Page 125 - 高中 信息技术 选择性必修1 数据与数据结构

 5.2 查找

（3） 若相等，则查找成功，返回该元素的下标。
（4） 若k< a[mid]，则将范围缩小到左子表a[0]~a[mid-1]。
（5） 若k> a[mid]，则将范围缩小到右子表a[mid+1]~a[n-1]。
（6） 迭代以上过程，直到找到k或当前查找区间为空（即查找失败）。
二分查找算法的过程如图5-6所示。

广东教育出版社

图5-6 二分查找流程图

二分查找算法的实现代码如下：
int binsearch(ShangPinType a[],int k,int n)
//在n个元素的数组a中二分查找k
{
int low=0,high=n-1; //待查区间下界、上界

while(low<=high)
{
int mid=(low+high)/2; //取待查区间内中间元素的下标

if(k==a[mid].BianHao) return mid; //中间元素即待找元素，返回mid值
else if(k<a[mid].BianHao) high=mid-1; //修改区间上界，在左子表
//继续查找
else low=mid+1; //修改区间下界，在右子表继续查找
}

return -1; //未找到，返回-1
}

117117

21X2204.indd 117 2019/9/26 13:53:38