Fibonacci查找

Fibonacci查找跟二分查找一样都是使用分治思想，其实都是每次查找的时候都是分两部分查找，二分查找使用的方式是分成等分的两部分，而Fibonacci查找使用的是Fibonacci数列划分。

为什么要按照Fibonacci数列划分呢？

下面先看看一个普通的二分查找：

未经优化的二分查找

可以证明二分查找的时间复杂度是o(logn)，考虑前面系数的话，大约是o(1.5logn)

我们观察到进入右边区间的经过一次判断，而进入左边区间的经过两次判断，也就是进入左侧和右侧区间的比较次数不一样。

我们进行优化的思路是什么？

1.使进入左侧和右侧的比较次数一样

2.尽量进入右侧判断

第一种方式后面再说，顺着第二种方式，我们使用Fibonacci数列进行分割，这就是Fibonacci查找。利用斐波那契数来对传入的数组进行黄金分割，这样前半部分较多而后半部分较少。如此一来，我们人为造成的这种不平衡，反倒是助长了搜索成本的平衡。

Fibonacci查找

对于任何A[0,n]，总是选取A[λn]为轴点，0<=λ<1

对于二分查找λ=0.5，对于Fibonacci查找λ=0.6108...

λ如何选值能达到最优，平均查找长度为a(λ)*log2

a(λ)*log2n = λ*[1+a(λ)*log2(λn)]*(1-λ)[2+a(λ)*log2(1-λ)n]

最后整理得出，a(λ)=1.4404...达到最优