算法笔记_二分查找/斐波那契查找

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