查找-之有序表查找

//C
int Binary_Search(int *a,int n,int key)
{
 int low,high,mid;
 //边界的界定
 low=1;
 high=n;
 while(low<=high)
 {
  mid=(low+high)/2
  if(key<a[mid])//待查的数小于中间的值，说明数据在待查表的左边
     high=mid-1;
  else if(key>a[mid])//待查的数大于中间的值，说明数据在待查表的右边
     low=mid+1;
  else
     return mid
 }
return 0;
}

//C
/*构造一个斐波那契数组*/
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];
}
int Fibonacci_Search(int *a, int n, int key)
 {
int low, high,mid,i,k;
low=1;//左边界
high=n;//右边界
int F[n];
Fibonacci(F);//构造一个斐波那契数组F
k=0;
while(n>F[k]-1)//计算n位于斐波那契数列的位置 
    k++;
for(i=n;i<F[k]-1;i++)//将待查数组长度不满（斐波那契数列中对应值--长度）的数值部分补全  ，也即是在a数组的尾部拷贝补充到指定F[k]-1长度
    a[i]=a[n];
while(low<=high)
{
  mid=low+F[k-1]-1;//计算当前分隔的下标
  if(key<a[mid])//若查找记录小于当前分隔记录，说明key在待查数组的前半部分
    {
     high=mid-1;//最高下标调整到分隔下标mid-1处
     k=k-1;//斐波那契数列的下标减1位
    }
  else if(key>a[mid])//若查找记录大于当前分隔记录，说明key在待查数组的后半部分
   {
    low=mid+1;
    k=k-2;
   }
 else
   {
      if(mid<=n)//若相等且小于长度n则说明mid为查找到的位置
         return mid;
     else//若mid>n说明是补全数值，返回待查数组的末尾的第一个数字索引n
       return n ;
   }
 }
return -1;
}