Fibonacci Search

2020-10-13

In the previous blog post Time complexity and shortcoming of Binary Search, we calculated that approximately the average search length is . The binary search algorithm can guarantee the asymptotic time complexity of even in the worst case, however, there is still room for optimization in terms of the cosntant coefficient .

Causes of the optimization

template <typename T>
Rank vector<T>::search(T const & e,Rank lo,Rank hi)     //binary search 
{
int mi;
while(lo<hi)                                            //change recursion to iteration 
{
	mi=(lo+hi)>>1;
	if(e<_elem[mi]) hi=mi;
	else if(e>_elem[mi]) lo=mi+1;
	else return mi;
 } 
 return -1;                                            //search failed 
}

As shown in the above code, it does 1 successful comparation and goes deep into the left side of or does 1 failure comparation and 1 successful comparation and then goes deep into the right side in each iteration before hitting the target. Obiviously, time cost would be reduced if we adjust the division method about the position of so that the first case is increased as much as possible.

Derivation

Considering the general situation, we can select as pivot for any vector , in which . For example, Binary Search corresponds to that .

Now the question is that what number between and equals so that the average search length can be the least.

接下来用递推分析法。对于长度为的有序向量，每一步迭代都有三种可能的分支：

经过次成功的比较，转化为一个规模为的新问题

经过次失败的比较和次成功的比较，转化为另一个规模为的新问题

经过次失败的比较，在当前位置命中
由以上分析可得递推式： $C(k)=[C(k-1)+(2^{k-1}-1)]+[2*(2^{k-1}-1)+C(k-1)]+2 \\ =2*C(k-1)+3*2^{k-1}-1$

Similarly, we can write down the recurrence formula:

$\alpha(\lambda)*log_{2} n*n= \\ [\alpha(\lambda)*log_{2} \lambda n*\lambda n+1*\lambda n]+ [\alpha(\lambda)*log_{2} (1-\lambda) n*(1-\lambda)n+2*(1-\lambda)n]$

Having had the formula modified:

$\frac{-ln2}{\alpha(\lambda)}=\frac{\lambda \cdot ln\lambda + (1-\lambda)\cdot ln(1-\lambda)}{2-\lambda}$

Using knowledeg of advanced mathmatics, it is calculated that obtains the minimun value when .
Therefore, Binary Search can be optimized as Fibonacci Search, which has average search legth of .

Implement

#include "fib.h"       // introduce Fibonacci sequence class
template<typename T>
static Rank FibSearch(T* A,T const& e, Rank lo, Rank hi)  // defined as static member function
{
    fib Fib(hi-lo);
    while(lo<hi)
    {
        while (hi-lo<Fib.get()) Fib.prev();   // sequential search forward
        Rank mi=lo+Fib.get()-1;    //  determine the pivot point like Fib(k)-1
        if (e<A[mi]) hi=mi;  //go deep into the
        else return mi;  //shot at mi
    }
    return -1;  //search failed
}