各种查找算法实现

1. 顺序查找(Sequential Search)，又叫线性查找

2. 二分查找，又叫折半查找

 1 package search;
 2 
 3 /**
 4  * @author lei 2011-8-17
 5  */
 6 public class BinarySearch {
 7     /**
 8      * 二分查找
 9      * 
10      * 注意：二分查找只是针对有序排列的各种数组或集合
11      * 
12      * @param target
13      * @param array
14      * @return
15      */
16     static boolean binarySearch(int target, int[] array) {
17         int front = 0;
18         int tail = array.length - 1;
19         // 判断子数组是否能再次二分
20         while (front <= tail) {
21             // 获取子数组的中间位置，并依据此中间位置进行二分
22             int middle = (front + tail) / 2;
23 
24             if (array[middle] == target) {
25                 return true;
26             } else if (array[middle] > target) {
27                 tail = middle - 1;
28             } else {
29                 front = middle + 1;
30             }
31         }
32         return false;
33     }
34 
35     public static void main(String[] args) {
36         int[] array = new int[] { 1, 2, 3, 5, 7, 9, 17, 121, 4545 };
37         System.out.println(binarySearch(4545, array));
38     }
39 }

Benary Search

3. 插值查找

4. 斐波那契查找

5. 线性索引查找：将索引项集合组织为线性结构，也称索引表

　　5.1 稠密索引：指在线性索引中，将数据集中的每个记录对应一个索引项

索引项一定是按照关键码有序排列的