折半查找法

折半查找又称为二分查找，要求：1.必须采用顺序存储结构；2.必须按照关键字大小有序排列
算法思想：首先将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前后两个子表，再按上述重复查找
折半查找优点是比较次数少，查找速度快，平均性能好
缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
非递归算法描述： 
binarysearch
low ←1;high ←n;j ←0
while (low≤high) and (j=0)
    mid ←(low+high)/2
    if  x=A[mid] then  j ←mid
    else if  x<A[mid] then high ←mid-1
   else low ←mid+1
end  while 
return  j
 

#include<iostream>
#define MAX_SIZE 100
using namespace std;
typedef struct{
    int r[MAX_SIZE];
    int length;
}SStable;

int BinSearch(SStable &ST,int k){
    int low,high,mid;
    low=1;
    high=ST.length;//给区间一个初始值
    while(low<=high){
        mid=(low+high)/2;
        if(k==ST.r[mid])
            retuen mid;
        else if(k<ST.r[mid])
            high=mid-1;
        else
            low=mid+1;
    }
    if(low>high)
        return 0;
    
}

int main(){
    SStable ST;
    int i,k,p;
    cin>>ST.length;
    for(i=1;i<=ST.length;i++)
        cin>>ST.r[i];
    cin>>k;
    p=BinSearch(ST,k);
    if(p==0)
        cout<<"该数不存在！"<<endl;
    else
        cout<<p<<endl;
    return 0;

}

递归算法描述：
If  low >high  then  return 0
 else
    mid ←(low+high)/2
    if  x=A[mid] then return mid
      else if x<A[mid] then return
                binarysearch(low,mid-1)
    else return  binarysearch(mid+1,high)
end  if

二分查找递归代码

int BinarySearch(SStable &ST,int k,int low,int high)
{
    if(low>high)
        return -1;
    else
    {
        if(ST.r[(low+high)/2]==k)
            return (low+high)/2;
        else if(k>ST.r[(left+right)/2])
            return BinarySearch(ST,k,(low+high)/2+1,high);
        else 
            return BinarySearch(ST,k,low,(low+high)/2-1);
    }
}

折半查找过程可用二叉判定树的描述，对其先序遍历。由于判定树的叶结点所在层次之差最多为1，所以不会超过log2n向下取整+1。