有序表查找

Wu Jun 2019-12-25 15:59:03
Categories: > > Tags:

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$

平均性能优于折半查找