版权声明：本文源自简书tianma，转载请务必注明出处：http://www.jianshu.com/p/a3bda7ba96ea
引言
如果待查找的数组是有序的，那么此时的查找就是有序表查找，这对于查找的帮助是很大的。属于有序表查找的有：折半查找（二分查找）、插值查找以及斐波那契查找。
1. 折半查找
折半查找又称为二分查找，是一种效率较高的查找算法。折半查找的先决条件是查找表中的数据元素排列必须是有序的。折半查找先以有序数列的中点位置为比较对象，如果要找的元素值小于中点位置元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，可以将查找的区间缩小一半，每次比较，都可以将当前查找范围缩小至一般，可以明显的减少比较的次数，提高查找效率。
时间复杂度：O(logn)
算法实现：
// 定义接口
interface Searcher {
/**
* 从数组array中查找关键字key,如果存在则返回该关键字在数组中任意出现的位置(不局限于首次或者末次之类的),否则返回-1
*/
int search(int[] array, int key);
}
/**
* 二分法查找,时间复杂度O(logn)
*/
class BinarySearcher implements Searcher {
// 二分法查找前提,查找表array是顺序(这里要求递增)排列的
@Override
public int search(int[] array, int key) {
int low, high, mid;
low = 0; // 定义最低下标为array首位
high = array.length - 1; // 定义最高下标为array末位
while (low <= high) {
mid = (low + high) / 2; // 折半
if (array[mid] > key) {
// 中值比key大,则high=mid-1
high = mid - 1;
} else if (array[mid] < key) {
// 中值比key小,则low=mid+1
low = mid + 1;
} else {
// 相等说明mid即为key在array中所在位置
return mid;
}
}
return -1;
}
}
2. 插值查找
插值查找是二分查找演化而来，相比于二分查找(折半),该算法考虑的是每次折的时候折多少,即不一定是1/2;如在一本字典中找"abstract"这个单词,我们自己来操作肯定是先翻到字典开始的那一小部分,而不是从字典的中间开始进行折半查找。
在二分查找中mid=(low+high)/2=low+1/2*(high-low),插值查找就是对1/2(系数,或者说比例)进行改变，它将1/2变成 (key - array[low])/(array[high] - array[low]),其实就是计算线性比例。
时间复杂度：O(logn)
因为插值查找是依赖线性比例的，如果当前数组分布不是均匀的，那么该算法就不合适。
算法实现：
class InterpolateSearcher implements Searcher {
@Override
public int search(int[] array, int key) {
int low, high, mid;
low = 0; // 定义最低下标为array首位
high = array.length - 1; // 定义最高下标为array末位
while (low <= high) {
// 相比二分法查找的更改处
mid = low + (int) (1.0 * (key - array[low]) / (array[high] - array[low]) * (high - low));
if (array[mid] > key) {
// 中值比key大,则high=mid-1
high = mid - 1;
} else if (array[mid] < key) {
// 中值比key小,则low=mid+1
low = mid + 1;
} else {
// 相等说明mid即为key在array中所在位置
return mid;
}
}
return -1;
}
}
3. 斐波那契查找
根据前面二分查找以及插值查找来看，有序表上的查找的关键就是如何分割当前查找的区域（二分查找对半分割，差值查找按线性比例分割），说到分割，还有一个著名的分割方式就是黄金分割。
斐波那契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、····，在数学上，斐波那契被递归方法如下定义：F(1)=1，F(2)=1，F(n)=f(n-1)+F(n-2) （n>=2）。该数列越往后相邻的两个数的比值越趋向于黄金比例值（0.618）
所以我们可以根据斐波那契数列对当前区域进行分割 :)
查找算法：在斐波那契数列找一个等于略大于查找表中元素个数的数F(n)，将原查找表扩展为长度为F(n)(如果要补充元素，则补充重复最后一个元素，直到满足数组元素个数为F(n)个元素)，完成后进行斐波那契分割，即F(n)个元素分割为前半部分F(n-1)个元素，后半部分F(n-2)个元素，找出要查找的元素在那一部分并递归，直到找到。
时间复杂度：O(logn)，平均性能优于二分查找。
算法实现：
class FibonacciSearcher implements Searcher {
private static final int MAX_ARRAY_SIZE = 30;
/**
* 得到长度为len的斐波那契数列
*
* @return
*/
private int[] fibonacci(int len) {
if (len < 0)
throw new IllegalArgumentException("length must bigger than 0");
int[] fibonacci = new int[len];
fibonacci[0] = 1;
fibonacci[1] = 1;
for (int i = 2; i < len; i++) {
fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
}
return fibonacci;
}
@Override
public int search(int[] array, int key) {
int low = 0; // 低位
int len = array.length;
int high = len - 1; // 高位
int mid; // 中间位
int k = 0; // 斐波那契数列下标(用于进行分割)
// 获取斐波那契数列
int[] fib = fibonacci(MAX_ARRAY_SIZE);
// 获取斐波那契数列分割点位置
while (len > fib[k] - 1) {
k++;
}
// 创建临时数组(数组长度为fib[k] - 1)
int[] tmp = new int[fib[k] - 1];
// 拷贝原数组到tmp数组中
System.arraycopy(array, 0, tmp, 0, len);
// 填充tmp数组中剩余的位置,补充的元素值为最后一个元素值
for (int i = len; i < fib[k] - 1; i++) {
tmp[i] = array[high];
}
// 开始进行类似于二分查找的查找
while (low <= high) {
// 对于tmp数组,整个数组的长度为fib[k]-1
// 而 fib[k]-1 = (fib[k-1]-1) + 1 + (fib[k-2]-1);
// 所以可以这样理解： mid下标对应元素可以将整个数组拆分为两部分,第1部分有fib[k-1]-1个元素,第2部分有fib[k-2]-1个元素
// mid=low+fib[k-1]-1; 正是将 数组的[low, max(high,tmp.length-1)]
// 部分按照斐波那契规则分为两部分
mid = low + fib[k - 1] - 1;
if (tmp[mid] > key) {
// 需要查找第1部分
high = mid - 1;
// fib[k] = fib[k-1] + fib[k-2]
// 第一部分有fib[k-1]个元素,所以将k-1赋值为k
k = k - 1;
} else if (tmp[mid] < key) {
// 需要查找第2部分
low = mid + 1;
// fib[k] = fib[k-1] + fib[k-2]
// 第二部分有fib[k-2]个元素,所以将k-2赋值给k
k = k - 2;
} else {
// 查找成功
// 以下代码其实就是返回 min(mid, high);
// return Math.min(mid, high);
if (mid <= high)
return mid;
else
return high; // 因为mid可能大于high,即查找到了补充的元素,那么还是应该返回high
}
}
return -1;
}
}
结束语
以上三种查找算法中，都依赖于顺序表，三者的区别本质上就是分割点选的不同。在分割点的选择中，折半查找 mid=(low+high)/2是加法与除法运算；插值查找mid = low+(key-array[low])/(array[high]-array[low])*(high-low)是复杂的四则运算；斐波那契查找mid=low+fib[k-1]-1是简单的加减运算。在海量数据查找过程中细微的差别会影响最终的效率。
三种查找算法，各有优劣，实际开发可以根据数据的特点综合考虑再做出选择。
