二分查找

二分查找又称折半查找，是一种效率较高的查找方法。二分查找的对象必须是顺序存储结构的有序表（不妨设为递增有序）

递归代码:

int BinSearch(SeqList R,KeyType k,int low,int high)
{
  int mid;
  if(low<high){
      mid = (low+high)/2;
      if(R[mid.key]==k) return mid;   //查找成功，返回其下标
      if(R[mid.key>k])
           return  BinSearch(R,k,low,mid-1);  //在左子表中继续查找
      else
           return  BinSearch(R,k,mid+1,high);   //在右子表中继续查找
  }else
      return 0;      //查找失败，返回0
}

非递归实现:

int Binsearch(SeqList R, KeyType  k, int n)
{
  int low =1, mid ,high=n;  //初始化上下界
  while(low<=high){
      mid=(low+high)/2;
      if(R[mid].key == k)   
            return mid;             //查找成功，返回其下标
      if(R[mid].key>k)
            high = mid-1;           //修改上界
      else   low=mid+1;          //修改下界
  }
  return 0;                             //查找失败，返回0；
}

时间复杂度可以表示为O(h)=O(log2n)