有序向量查找算法

目录

fibSearch：按黄金分割点取mi 

binSearch ：按平均数取mi

二分查找

插值查找

原理​

性能​

fibSearch：按黄金分割点取mi 

binSearch ：按平均数取mi，二分查找

 The binary search generally selects the midpoint as mi, and the Fibonacci search uses the Fibonacci sequence to select a positionally non-equilibrium mi.

In binsearch(e, lo, hi) version A, if V[mi] < e, then the next search range is: V(mi, hi) 

For binary search version C, what is the next search range when e<V[mi] is not established: V(mi, hi)

 二分查找相当于一个AVL，所以复杂度就等于BBST的高度O（logn）。

插值查找

原理

性能