斐波那契查找

上一节我们讨论了二分查找,其平均查找长度是 $\mathcal{O}(1.5 \log{}n) $,这种最基本的二分查找仍有改进余地,我们可以通过斐波那契查找来改进二分查找。

仔细观察每次查找的比较情况,向左查找需要比较一次,向右查找需要比较两次。转向左右分支的比较次数不同,但是递归深度却是相同的,那么两侧元素的查找成本相差很多。这种差异下,所有情况的查找成本平均起来也不是最小的。

如果我们能够减小右侧情况的查找成本,分摊到左侧,使左右两侧的查找成本更接近,那么总体的平均查找成本会小一些。

斐波那契查找就是这种思想的查找算法。借助来斐波那契数的特性 $(F(n) = F(n-1) + F(n-2))$,来优化二分查找。