首页 > 其他 > 详细

二分查找

时间:2018-08-18 19:28:06      阅读:139      评论:0      收藏:0      [点我收藏+]

对于一个有序的序列,可以用二分查找的方式快速找到某一元素。顾名思义,二分查找就是利用二分的思想,通过将要查找的元素与区间中点值比较,大体确定元素位置,舍弃一半的元素,因此效率很高。

c++ STL库中提供了这类函数:lower_bound和upper_bound。其中lower_bound是返回有序序列中某元素出现的第一个位置,而upper_bound返回的是某元素出现的最后一个位置的下一个位置。若序列中没有要查找的元素,则会返回一个位置i,使得在i处插入该元素,并将原来的a[i],a[i+1],...向后移动后,序列仍然有序。

其实,这两个函数也可以自己实现。

 1 int lower_bound(int x) {
 2     int l=1,r=n,m;
 3     while(l!=r) {
 4         m=l+(r-l)/2;
 5         if(a[m]>=x) r=m;
 6         else l=m+1;
 7     }
 8     return l;
 9 }
10 
11 int upper_bound(int x) {
12     int l=1,r=n,m;
13     while(l!=r) {
14         m=l+(r-l)/2;
15         if(a[m]<=x) l=m+1;
16         else r=m;
17     }
18     return l;
19 }

关键在于更新区间范围的时候,以lower_bound为例,当a[m]=x时,说明找到了一个x,而左边可能还有,因此r=m;当a[m]>x时,说明该元素可能在左侧,同上;当a[m]<x时,说明该元素在右侧,因此l=m+1。

二分查找

原文:https://www.cnblogs.com/Mr94Kevin/p/9498116.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!