有序表查找

1 折半查找(二分查找)

折半查找：又称为二分查找。在有序顺序存储的线性表中，取中间记录作为比较对象，若相等,则成功；若给小于，则在左半区继续查找；若给大于，则在右半区继续查找。

$mid = \frac{low+high}{2}= low+\frac{1}{2}(high-low)$

适合有序，静态查找表。 不适合动态查找表。

2 插值查找

插值查找：是根据要查找的关键字 key 与查找表中最大最小记录的关键字比较后的查找方法，不直接一半

$mid = low+\frac{key-a[low]}{a[high]-a[low]}(high-low)$

适合表长较大，而关键字分布又比较均匀的查找表。 不适合极端不均匀的数据。

3 斐波那契查找

假设有待查找数组 array[n] 和斐波那契数组 F[k]，n 不大于 F[k]-1，若 n 小于F[k]-1，array[n+i] 补足到 array[F[k]-1]，值都为array[n]。

$mid = low + F[k-1]-1$

平均性能优于折半查找