二分查找

要求给定已按升序排好序的n个元素a[0:n-1]，现要在这n个元素中找出一特定元素e。

普通版本：

int BinSearch(int *a,int e,int lo,int hi)
{
    if(hi-lo<0) return -1;
    while(lo<hi)
    {
        int mi=(lo+hi)>>1;
        if(e<a[mi]) hi=mi-1; //这里两个<可以描绘出e所查找的空间范围
        if(a[mi]<e) lo=mi+1;
        else return mi;
    }
    return -1;
}

不足：binSearch版本的查找过程不平衡：向左、向右两个分支所需要的比较次数不相等，向左比较1次，向右比较2次。

改进1：斐波拉契查找

改进方法：利用斐波拉契数列确定轴点，使得转向更多地集中在比较次数较少的向左。
思路：要求开始表中记录的个数为某个斐波那契数小1，即n=Fk-1;
开始将key值与第F(k-1）位置的记录进行比较(即mid=low+F(k-1)-1),比较结果也分为三种：
1、key == arr[mid]，mid位置的元素即为所求
2、key > arr[mid]，low=mid+1，k-=2
low=mid+1：说明待查找的元素在[mid+1,high]范围内
k-=2：说明范围[mid+1,high]内的元素个数为n-（F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找
3、key < arr[mid]，high=mid-1，k-=1
low=mid+1：说明待查找的元素在[low,mid-1]范围内
k-=1：说明范围[low,mid-1]内的元素个数为F(k-1)-1 个，所以可以递归 的应用斐波那契查找

const int max_size=20;//斐波那契数组的长度  

//构造一个斐波那契数组 
void Fibonacci(int* F)  
{  
    F[0]=0;  
    F[1]=1;  
    for(int i=2;i<max_size;++i)  
        F[i]=F[i-1]+F[i-2];  
}  

//斐波那契查找
//arr为要查找的数组,n为要查找的数组长度,key为要查找的关键字  
int FibonacciSearch(int* arr, int n, int key)  
{  
  int low=0, high=n-1;  
  int mid = 0;
  //构造一个斐波那契数组F 
  int F[max_size];  
  Fibonacci(F);              

  //计算n位于斐波那契数列的位置
  int k=0;  
  while(n>F[k]-1)            
      ++k;  

  //将数组arr扩展到F[k]-1的长度 
  int* temp;              
  temp=new int [F[k]-1];  
  memcpy(temp,arr,n*sizeof(int));  
  for(int i=n;i<F[k]-1;++i)  
      temp[i]=arr[n-1];  

  while(low<=high)  
  {  
      mid=low+F[k-1]-1;  
      if(key < temp[mid])  
      {  
          high = mid-1;  
          k -= 1;  
      }  
      else if(key > temp[mid])  
      {  
          low = mid+1;  
          k -= 2;  
      }  
      else  
      {  
          if(mid<n)  
              return mid; //若相等则说明mid即为查找到的位置  
          else  
              return n-1; //若mid>=n则说明是扩展的数值,返回n-1  
      }  
  }    
  delete[] temp;  
  return -1;  
} 

改进2：左右两次平衡

思路：牺牲mi处的最好情况。