二分查找也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。
二分查找时间复杂度 O(logn)
注意：要求数组是有序的
/**
* 二分查找
* 注意：要求数组是有序的
*
* @param arr 从这个数组中查找
* @param key 要查找的值
* @return 查找结果(key的下标位置), 查找失败返回 -1
*/
public static int binarySearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
int midVal = arr[mid];
if (midVal == key) { // 若相等则说明mid即为查找到的位置
return mid;
} else if (midVal < key) {
low = mid + 1;
} else { // midVal > key
high = mid - 1;
}
}
return -1;
}使用递归实现
/**
* 二分查找(递归版)
* 注意：要求数组是有序的
*
* @param arr 从这个数组中查找
* @param low 索引起始位置
* @param high 索引结束位置
* @param key 要查找的值
* @return 查找结果(key的下标位置), 查找失败返回 -1
*/
public static int binarySearchRecursion(int[] arr, int low, int high, int key) {
if (low <= high) {
int mid = (low + high) / 2;
int midVal = arr[mid];
if (midVal == key) {
return mid;
} else if (midVal < key) {
low = mid + 1;
return binarySearchRecursion(arr, low, high, key);
} else { // midVal > key
high = mid - 1;
return binarySearchRecursion(arr, low, high, key);
}
}
return -1;
}其实二分查找、插值查找以及斐波那契查找都可以归为一类——有序表查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。
二分查找的推广，有时候不一定折半最优。 $$ mid = \frac{low + high}{2} = low + \frac{1}{2}(high - low) $$
也就是mid等于最低下标low加上最高下标high与low的差的一半。1/2可以进行改进，改进为下面的计算方案： $$ mid = \frac{low + high}{2} = low + \frac{key - a[low]}{a[high] - a[low]}(high - low) $$ 相应代码需要改写为
int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]); 时间复杂度也是O(logn)，但对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好得多。反之，数组中如果分布类似{0,1,2,2000,2001,......,999998,999999}这种极端不均匀的数据，用插值查找未必是很合适的选择。
斐波那契查找也叫做黄金分割法查找，它也是根据折半查找算法来进行修改和改进的。
对于斐波那契数列：1、1、2、3、5、8、13、21、34、55、89……（也可以从0开始），前后两个数字的比值随着数列的增加，越来越接近黄金比值0.618。比如这里的89，把它想象成整个有序表的元素个数，而89是由前面的两个斐波那契数34和55相加之后的和，也就是说把元素个数为89的有序表分成由前55个数据元素组成的前半段和由后34个数据元素组成的后半段，那么前半段元素个数和整个有序表长度的比值就接近黄金比值0.618，假如要查找的元素在前半段，那么继续按照斐波那契数列来看，55 = 34 + 21，所以继续把前半段分成前34个数据元素的前半段和后21个元素的后半段，继续查找，如此反复，直到查找成功或失败，这样就把斐波那契数列应用到查找算法中了。
/**
* 斐波那契查找
* 注意：要求数组是有序的
*
* @param arr 从这个数组中查找
* @param key 要查找的值
* @return 查找结果(key的下标位置), 查找失败返回 -1
*/
public static int FibonacciSearch(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
int mid = 0;
// 斐波那契分割数值下标
int k = 0;
// 序列元素个数
int i = 0;
// 获取斐波那契数列
int[] f = fibonacci();
// 获取斐波那契分割数值下标
while (arr.length > f[k] - 1) {
k++;
}
// 创建临时数组
int[] temp = new int[f[k] - 1];
for (int j = 0; j < arr.length; j++) {
temp[j] = arr[j];
}
// 序列补充至f[k]个元素
// 补充的元素值为最后一个元素的值
for (i = arr.length; i < f[k] - 1; i++) {
temp[i] = temp[high];
}
System.out.println("序列补充 " + Arrays.toString(temp));
System.out.println("获取斐波那契数列 " + Arrays.toString(f));
while (low <= high) {
// low：起始位置
// 前半部分有f[k-1]个元素，由于下标从0开始
// 则-1 获取 黄金分割位置元素的下标
mid = low + f[k - 1] - 1;
if (temp[mid] > key) {
// 查找前半部分，高位指针移动
high = mid - 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] = f[k-1] + f[k-1]
// 因为前半部分有f[k-1]个元素，所以 k = k-1
k = k - 1;
} else if (temp[mid] < key) {
// 查找后半部分，高位指针移动
low = mid + 1;
// （全部元素） = （前半部分）+（后半部分）
// f[k] = f[k-1] + f[k-1]
// 因为后半部分有f[k-1]个元素，所以 k = k-2
k = k - 2;
} else {
//如果为真则找到相应的位置
if (mid <= high) {
return mid;
} else {
//出现这种情况是查找到补充的元素
//而补充的元素与high位置的元素一样
return high;
}
}
}
return -1;
}
public final static int MAXSIZE = 20;
/**
* 斐波那契数列
*
* @return
*/
public static int[] fibonacci() {
int[] f = new int[MAXSIZE];
int i = 0;
f[0] = 1;
f[1] = 1;
for (i = 2; i < MAXSIZE; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f;
}斐波那契查找算法的核心在于：
1）当key=a[mid]时，查找就成功；
2）当key<a[mid]时，新范围是第low个到第mid-1个，此时范围个数为F[k-1]-1个；
3）当key>a[mid]时，新范围是第m+1个到第high个，此时范围个数为F[k-2]-1个。
二分查找是进行加法与除法运算（mid=(low＋high)/2），插值查找进行复杂的四则运算（mid=low＋(high-low)*(key-a[low])/(a[high]-a[low])），而斐波那契查找只是最简单加减法运算（mid=low＋F[k-1]-1），在海量数据的查找过程中，这种细微的差别可能会影响最终的查找效率。