二分查找及其应用举例

二分查找是在一个排序数组中查找一个给定键值为key的元素的快速算法：
int binary_search(item_type s[],item_type key,int low,int high)
{
int mid;
if(low>high) return -1;
mid=(low+high)/2;
if(s[mid]==key) return mid;
if(s[mid]>key)
        return binary_search(s,key,low,mid-1);
else
        return binary_search(s,key,mid+1,high);
}
迭代实现：
int binary_search(item_type s[],item_type key,int len)
{
int low,mid,high;
low=0;
high=len-1;
while(low<=high)
{
        mid=(low+high)/2;
        if(s[mid]==key) return mid;
        if(s[mid]>key)
               high=mid-1;
        else
               low=mid+1;
}
return -1;
}
应用举例：
查找某个键值为key的元素在排序数组中出现的次数：
利用二分查找分别找到这个元素在排序数组中最左边的下标left和最右边的下标right(为最右边的键值为key的下一个元素的下标)，出现次数=right-left；
int search_right(item_type s[],item_type key,int low,int high)
{
int mid;
if(low>high) return low;
mid=(low+high)/2;
if(s[mid]>key)
        return binary_search(s,key,low,mid-1);
else
        return binary_search(s,key,mid+1,high);
}
int search_left(item_type s[],item_type key,int low,int high)
{
int mid;
if(low>high) return low;
mid=(low+high)/2;
if(s[mid]<key)
       return binary_search(s,key,mid+1,high);
else
       return binary_search(s,key,low,mid-1);
}
int find_keynum(item_type s[],item_type key,int len)
{
if(s==NULL||len<=0)
       return -1;
int right=search_right(s,key,0,len-1);
int left=search_left(s,key,0,len-1);
if(s[left]==key)
      return right-left;
else
      return -1;
}

补充：综合编程 , 其他综合 ,