有序表查找

二分查找插值查找斐波那契查找性能对比

1、二分查找

又称折半查找，它的前提是线性表必须采用顺序存储。基本思想是每一次都去的序列的中间位置的关键字进行比较，然后根据大小进行序列的更新，如此不断循环，直到最后。

1、在有序序列中取中间位置作为比较对象，若待查找对象与该对象相等，则查找成功。

2、若待查找对象小于中间对象，则在中间对象的左半区继续重复步骤1，进行查找。

3、若待查找对象大于中间对象，则在中间对象的右半区继续重复步骤1，进行查找。

4、不断重复上述过程，直到查找成功，若无相等对象则查找失败。

实现代码如下所示：

int Binary_Search(int *a, int n; int key) { int low, high, mid; low = 1; high = n; while (low < high) { mid = (low + high) / 2; //折半，这里每次都取得是中间位置 if (key < a[mid]) //下一次循环，取在中间对象的左半区 high = mid - 1; else if (key>a[mid]) //下一次循环，取在中间对象的右半区 low = mid + 1; else return mid; } return 0; }

2、差值查找

这是一种对二分查找（折半查找）的改进形式，插值查找的每次选取的比较对象不再是序列的正中间位置，而是与待查找的key值有关。

可以进行对比，二分查找的中间位置可以表示为：

现在的插值查找的位置变成如下形式：

实现代码只需修改一行即可：

mid = mid = low + (high - row)*(key - a[low]) / (a[high] - a[low]); //插值

对于表比较长，而关键字又分布比较均匀的查找表来说，插值算法的平均性能会比折半查找要好，但是对于分布比较极端不均匀的数据，插值法不一定是合适的。

3、斐波那契查找

这是一种利用黄金分割原来来实现查找的方法。

斐波那契数列：

实现代码如下所示：

int Fibonacci_Search(int *a, int n; int key) { int low, high, mid, i, k; low = 1; high = n; k = 0; while (n > F[k] - 1) //计算n位于斐波那契数列中的位置 k++; for (i = n; i < F[k] - 1; i++) //将不满的数值补全 a[i] = a[n]; while (low < high) { mid = low + F[k-1]-1; //计算当前分割符的下标 if (key < a[mid]) { high = mid - 1; k = k - 1; } else if (key>a[mid]) { low = mid + 1; k = k - 2; } else { if (mid <= n) return mid; else return n; } } return 0; }

就平均性能而言，斐波那契查找要优于折半查找，但是如果是最坏的情况，比如key=1.那么始终处于左侧长半区查找，查找效率要低于折半查找。

4、性能比较

折半查找是进行加法和除法运算（mid=（low+high）/2）,插值查找则进行复杂的四则运算（mid=low+（high-low）*（key-a[low])/(a[high]-a[low]））, 而斐波那契查找只是进行最为简单的的加减法运算（mid=low+F[k-1]-1）, 在海量的数据查找中，会很大程度的影响效率，虽然它们的时间复杂度均为O（logn）。