Java 中的查找算法（4种）
一，顺序查找 （暴力递归）
查找算法中顺序查找算是最简单的了，无论是有序的还是无序的都可以，只需要一个个对比即可，但其实效率很低
code
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;
二，二分法查找 **********
二分法查找适用于大的数据，但前提条件是 "数据必须是有序的" ，他的原理是先和中间的比较，如果等于就直接返回，如果小于就在前半部分继续使用二分法进行查找，如果大于则在后半部分继续使用二分法进行查找
code
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); // 防止 int（2^31-1） 溢出
if (value == array[middle]) {
return middle;
}
if (value > array[middle]) {
low = middle + 1;
}
if (value < array[middle]) {
high = middle - 1;
}
}
return -1;
// return ~low 返回的是要查询的数据应该存在方的位置
}
三，插值查找
二分法查然效率很高，但我们为什么要和中间的值进行比较，如果我们和数组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)，我们来看下插值查找的代码。
他和二分法查找代码很相似，只不过计算middle的方式不一样
code
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，后面多余的我们都用原数组最后的那个值填充
