算法笔记_二分查找/斐波那契查找
1. 查找
问题定义：在非降序数组中，找出指定的元素，如从{1,2,3,6,8,12}中找出元素2的位置。
二分查找的复杂度（比较次数，又称查找长度）是O(1.5log(n))，但不是最优的。改进：fibonacci数列进行改进。
原因：对于一个非降序数组，二分查找向左查找。需要比较1次，而向右查找，需要比较2次，存在不平衡，而我们希望，正确的比较（向左查找）的次数多一些，所以，不再使用从中间元素分成两半，进行查找，而是以fibonacci数列的值（1、1、2、3、5、8、13、21、34）作为划分数组的依据。如假设待查找数组的长度是21-1=20，第一次二分的点是13-1=12的位置，依次类推。
2. 例子
分别计算成功命中/未命中的查找次数，向左走，比较1次；向右走，比较2次。算得查找长度比二分查找略小（4.00<4.14）
3 代码实现
与二分查找，唯一的不同在于分割点 middle point 取的是fibonacci数列中的点（黄金分割点，又叫轴点）。
4 推广与证明
二分查找与fibonacci数列查找的区别，在于分割点的选择上，我们将其设为λ，则查找的复杂度为 a(λ)log(n) 列出递推式，求解关于λ的系数函数a(λ)，使其最小，可证明正好当λ=0.618是，a(λ)最小，即最优复杂度为1.44log(n).