二分查找
二分查找分为整数二分和小数二分,其中整数二分涉及的边界问题比较多,理解起来相对复杂。
# 整数二分
![](/i/ll/?i=img_convert/9e76e7b983ea015f807e9ca327a30cad.png)
如果可以找到一个性质,可以把区间一分为二,一半满足性质一半不满足。二分可以找到这个性质的边界,可以是①也可以是②。
这里这个分界点①和②就分两种情况讨论。
# 寻找边界点①——右边界
-
mid = (l + r + 1) >> 1
- 关于为什么需要
+1
是一个边界问题,可以看后面需要斟酌的细节
- 关于为什么需要
-
if( check(mid) )
有两种结果-
true
>>>[mid, r]
>>>l = mid
mid
满足性质,因此mid
落在红色区间,并且在红色区间可以取到边界点①,因此下一个区间包含mid
,区间为[mid, r]
。 -
false
>>>[l, mid - 1]
>>>r = mid - 1
mid
不满足性质,因此mid
落在绿色区间,在绿色区间内不可能取到边界点①,因此下一个区间不包含mid
,区间为[l, mid - 1]
。
-
# 寻找边界点②——左边界
-
mid = (l + r) >> 1
-
if ( check(mid) )
有两种结果-
true
>>>[l, mid]
>>>r = mid
mid
满足性质,因此mid
落在绿色区间,并且在绿色区间内可以取到边界点②,所以下一个区间包含mid
,区间为[l, mid]
。 -
false
>>>[mid + 1, r]
>>>l = mid + 1
mid
不满足性质,因此mid
落在红色区间,并且在红色区间内不可能取到边界点②,所以下一个区间不包含mid
,区间为[mid + 1, r]
。
-
# 步骤
一般情况下,先写一个mid
的取值,然后再写check()
函数的实现,及需要满足的性质。根据check()
的返回值判断区间如何划分。
A. 先确定序列的上下界
int l = 0, r = n - 1;
B. 开始查找,直接写出一个mid
,之后再看看用不用+1
int l = 0, r = n - 1;
while( l < r ) {
int mid = l + r >> 1;
}
C. 判断是要找性质的左边界还是右边界。
比如找左边界,即第一个>=x
的数。这里就开始讨论两种区间更新的情况,可以直接画出序列上面满足性质和不满足性质的区间图,然后再判断l, r
的更新方式。
- 如果
mid
落在>=x
的区间上,则x
在mid
的左边,同时mid
和x
在同个区间上,因此收缩r
时r = mid
- 如果
mid
没有落在>=x
的区间上,则x
在mid
的右边,而且mid
和x
不在同一个区间上,因此收缩l
时l = mid + 1
最后再看看mid
的更新方式要不要+1
,可以直接记:寻找性质左边界时不需要 +1
,或者是当更新区间的时候如果没有出现l, r
其中一个更新为“mid - 1
”,则不用在前面+ 1
。
int l = 0, r = n - 1;
while( l < r ) {
int mid = l + r >> 1;
if(q[mid] >= x) r = mid;
else l = mid + 1;
}
D. 在查找结束后,l
和r
会重叠指向我们要查找的性质的边界。若目标x
存在,则可以直接输出x
的位置。若目标不存在,则会返回第一个大于x
的数。
int l = 0, r = n - 1;
while( l < r ) {
int mid = l + r >> 1;
if(q[mid] >= x) r = mid;
else l = mid + 1;
} //then l == r
if(q[l] == x) cout << l << endl;
# 需要斟酌的细节
mid = (l + r) >> 1 还是 mid = (l + r + 1) >> 1
还是这个图
![](/i/ll/?i=img_convert/c72fbb281fd9538406d0fd3021919c6e.png)
在寻找边界点①的时候,当更新到l + 1= r
的时候,即l
与r
相邻时,如果mid
满足红色性质,则更新区间为[mid, r]
,也就是把l
更新成mid
。
如果使用mid = (l + r) >> 1
,由于整数除法是下取整, 因此把l
更新成mid
会有:l = mid = (l + (l+1) ) >> 1 = (2l + 1) >> 1 = l
.
也就是l = l
,相当于没有更新区间,因此会不停的执行mid = (l + r) >> 1
, l = mid
陷入死循环。
因此需要使用mid = (l + r + 1) >> 1
使得mid
的结果是区间的一半的上取整。这样区间的左边界才会收缩。
可以这么理解记忆:
-
当寻找性质的左边界的时候,由于更新区间为
r = mid, l = mid + 1
,此时mid = l + r >> 1
,不需要加一。- 为什么?
- 因为不加一的时候
mid
是下取整 - 更新
r
时直接赋值为mid
的也会下取整,因此r
一定会收缩,不会死循环。 - 更新
l
时是赋值为mid + 1
会上取整,因此l
也一定会收缩,所以mid
不需要加一。
-
当寻找性质的右边界的时候,由于更新区间为
l = mid, r = mid - 1
,此时mid = l + r + 1 >> 2
,需要加一。- 为什么?
- 因为加一的时候
mid
是上取整 - 更新
l
时直接赋值为mid
也会上取整,因此l
一定会收缩,不会死循环。 - 更新
r
时赋值为mid - 1
会抵消掉上取整,因此r
也一定会收缩。
# 查找结束时 l 和 r 的位置
由于循环的条件时l < r
,然后更新区间都会在[l, r]
之间更跟新,因此最终循环结束时必定有l == r
,因此最终的结果在 l
或者 r
上任意一个。
# 代码模板
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
2022.04.11
标签:二分,int,mid,更新,边界点,查找,区间,性质 From: https://www.cnblogs.com/Ethan-Code/p/16612631.html