上一节我们讨论了二分查找，其平均查找长度是 $\mathcal{O}(1.5 \log{}n) $，这种最基本的二分查找仍有改进余地，我们可以通过斐波那契查找来改进二分查找。
仔细观察每次查找的比较情况，向左查找需要比较一次，向右查找需要比较两次。转向左右分支的比较次数不同，但是递归深度却是相同的，那么两侧元素的查找成本相差很多。这种差异下，所有情况的查找成本平均起来也不是最小的。
如果我们能够减小右侧情况的查找成本，分摊到左侧，使左右两侧的查找成本更接近，那么总体的平均查找成本会小一些。
斐波那契查找就是这种思想的查找算法。借助来斐波那契数的特性 $(F(n) = F(n-1) + F(n-2))$，来优化二分查找。