“责人之心责己，恕己之心恕人。”
正文
一，顺序查找
查找算法中顺序查找算是最简单的了，无论是有序的还是无序的都可以，只需要一个个对比即可，但其实效率很低。我们来看下代码
1
2
3
4
5
6
7
public static int search(int[] a, int key) {
for (int i = 0, length = a.length; i < length; i++) {
if (a[i] == key)
return i;
}
return -1;
}
还有说上面的代码可以优化，使用一个哨兵，免去了每次都要越界的判断，但通过实际测试运行效率并没有提高，无论测试的数据是多还是少运行的时间都差不多，我们来看下代码。
1
2
3
4
5
6
7
8
9
public static int search(int[] a, int key) {
int index = a.length - 1;
if (key == a[index])
return index;
a[index] = key;
int i = 0;
while (a[i++] != key) ;
return i == index + 1 ? -1 : i - 1;
}
虽然是无序的，但如果我们知道要查找的数据出现在后面的概率比较大的话，我们还可以从后面进行查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int search(int[] a, int key) {
for (int i = a.length - 1; i >= 0; i--) {
if (a[i] == key)
return i;
}
return -1;
}
public static int search(int[] a, int key) {
if (key == a[0])
return 0;
int index = a.length - 1;
a[0] = key;
while (a[index--] != key) ;
return index == -1 ? index : index == 0 ? 1 : index + 1;
}
二，二分法查找
二分法查找适用于大的数据，但前提条件是数据必须是有序的，他的原理是先和中间的比较，如果等于就直接返回，如果小于就在前半部分继续使用二分法进行查找，如果大于则在后半部分继续使用二分法进行查找……我们来看下代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int binarySearch(int[] array, int value) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int middle = (low + high) >> 1;
if (value == array[middle]) {
return middle;
}
if (value > array[middle]) {
low = middle + 1;
}
if (value < array[middle]) {
high = middle - 1;
}
}
return -1;
}
但这样写会有个问题，当数据比较大并且要查找的值在后面的时候，求middle可能会出现溢出，所以一般情况下我们要这样写。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int binarySearch2(int[] array, int value) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int middle = low + ((high - low) >> 1);
if (value == array[middle]) {
return middle;
}
if (value > array[middle]) {
low = middle + 1;
}
if (value < array[middle]) {
high = middle - 1;
}
}
return -1;
}
在Android中有个类ArrayMap，看过他的源码的都知道，这里面也有个二分查找，因为他存储的时候key值要进行排序的，如果想了解更多，可以看下Android ArrayMap源码详解，也可以百度搜下。我们来看下他的二分查找代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// This is Arrays.binarySearch(), but doesn't do any argument validation.
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
我们看到如果没查到，返回的不是-1而是~lo，这里的~lo肯定是个负数，也就是说如果返回的是一个负数就表示没有找到，如果返回的是一个非负数就表示查找到了。如果是负数我们可以对他取反，他表示的就是要查找的数如果放到数组中应该存放到的位置。比如数组[2,5,6,8,9]，如果我们查找的是6就会返回6的下标2，如果查找的是4，就返回返回-2，为啥是-2，因为-2取反就是1，也就是如果把4存放到数组中应该存放到数组下标为1的位置。
上面都是非递归的写法，下面来看一下递归的写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int binarySearch4(int[] array, int value) {
int low = 0;
int high = array.length - 1;
return searchmy(array, low, high, value);
}
private static int searchmy(int array[], int low, int high, int value) {
if (low > high)
return -1;
int mid = low + ((high - low) >> 1);
if (value == array[mid])
return mid;
if (value < array[mid])
return searchmy(array, low, mid - 1, value);
return searchmy(array, mid + 1, high, value);
}
三，插值查找
二分法查然效率很高，但我们为什么要和中间的值进行比较，如果我们和数组1/4或者3/4部分的值进行比较可不可以呢，对于一个要查找的数我们不知道他大概在数组的什么位置的时候我们可以使用二分法进行查找。但如果我们知道要查找的值大概在数组的最前面或最后面的时候使用二分法查找显然是不明智的。比如我们查字典的时候如果是a或者b开头的我们一般会在前面找，如果是y或者z开头的我们一般偏向于往后面找，这个时候如果我们使用二分法从中间开始找显然是不合适的。之前二分法查找的时候我们比较的是中间值，mid=low+1/2(high-low);但插值查找的时候我们比较的不是中间值，是mid=low+(key-a[low])/(a[high]-a[low])(high-low)，我们来看下插值查找的代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int insertSearch(int[] array, int key) {
return search(array, key, 0, array.length - 1);
}
private static int search(int[] array, int key, int left, int right) {
while (left <= right) {
if (array[right] == array[left]) {
if (array[right] == key)
return right;
else return -1;
}
int middle = left + ((key - array[left]) / (array[right] - array[left])) * (right - left);
if (array[middle] == key) {
return middle;
}
if (key < array[middle]) {
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
}
他和二分法查找代码很相似，只不过计算middle的方式不一样。再来看一下递归的版本
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int insertSearch(int[] array, int key) {
return search2(array, key, 0, array.length - 1);
}
private static int search2(int array[], int key, int left, int right) {
if (left > right)
return -1;
if (array[right] == array[left]) {
if (array[right] == key)
return right;
else return -1;
}
int mid = left + (key - array[left]) / (array[right] - array[left]) * (right - left);
if (array[mid] == key)
return mid;
if (array[mid] > key)
return search2(array, key, left, mid - 1);
return search2(array, key, mid + 1, right);
}
四，斐波那契查找
斐波那契数列我们都知道{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 }，前后的比值会越来越接近0.618，也就是黄金分割点。0.618也被公认为最具有审美意义的比例数字。斐波那契查找原理其实和二分法查找原理差不多，只不过计算中间值mid的方式不同，还有一点就是斐波那契查找的数组长度必须是f（k）-1，这样我们就可以把斐波那契数列进行划分f（k）-1=f（k-1）+f（k-2）-1=（f（k-1）-1）+1+（f（k-2）-1）；然后前面部分和后面部分都还可以继续进行划分。但实际上我们要查找的数组长度不可能都是f（k）-1，所以我们要补齐最后的部分，让数组的长度等于f（k）-1，让数组的最后一位数字把后面铺满。比如我们查找的数组长度是21，而f（8）-1=21-1=20；小于21，所以f（8）-1是不行的，我们需要把数组长度变为f（9）-1=34-1=33，后面多余的我们都用原数组最后的那个值填充。我们来看下代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public static int fibonacciSearch(int[] array, int key) {
if (array == null || array.length == 0)
return -1;
int length = array.length;
int k = 0;
while (length > fibonacci(k) - 1 || fibonacci(k) - 1 < 5) {
k++;
}
int[] fb = makeFbArray(fibonacci(k) - 1);
int[] temp = Arrays.copyOf(array, fb[k] - 1);
for (int i = length; i < temp.length; i++) {
temp[i] = array[length - 1];//用原数组最后的值填充
}
int low = 0;
int hight = length - 1;
while (low <= hight) {
int middle = low + fb[k - 1] - 1;
if (temp[middle] > key) {//要查找的值在前半部分
hight = middle - 1;
k = k - 1;
} else if (temp[middle] < key) {//要查找的值在后半部分
low = middle + 1;
k = k - 2;
} else {
if (middle <= hight) {
return middle;
} else {
return hight;
}
}
}
return -1;
}
private static int fibonacci(int n) {
if (n == 0 || n == 1)
return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static int[] makeFbArray(int length) {
int[] array = new int[length];
array[0] = 0;
array[1] = 1;
for (int i = 2; i < length; i++)
array[i] = array[i - 1] + array[i - 2];
return array;
}
其实斐波那契查找效率并没有那么高，我们再来看一下斐波那契查找的递归实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public static int search(int[] array, int value) {
if (array == null || array.length == 0) return -1;
int length = array.length;
int k = 0;
while (length > fibonacci(k) - 1 || fibonacci(k) - 1 < 5) {
k++;
}
int[] fb = makeFbArray(fibonacci(k) - 1);
int[] temp = Arrays.copyOf(array, fb[k] - 1);
for (int i = length; i < temp.length; i++) {
temp[i] = array[length - 1];//用原数组最后的值填充
}
return fibonacciSearch(temp, fb, value, 0, length - 1, k);
}
public static int fibonacciSearch(int[] array, int[] fb, int value, int low, int hight, int k) {
if (value < array[low] || value > array[hight] || low > hight) return -1;
int middle = low + fb[k - 1] - 1;
if (value < array[middle]) {
return fibonacciSearch(array, fb, value, low, middle - 1, k - 1);
} else if (value > array[middle]) {
return fibonacciSearch(array, fb, value, middle + 1, hight, k - 2);
} else {
if (middle <= hight) {
return middle;
} else {
return hight;
}
}
}
private static int fibonacci(int n) {
if (n == 0 || n == 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static int[] makeFbArray(int length) {
int[] array = new int[length];
array[0] = 0;
array[1] = 1;
for (int i = 2; i < length; i++) array[i] = array[i - 1] + array[i - 2];
return array;
}
