二分的本质
二分的本质是寻找边界:给定一个区间,给定某一性质,这个性质可以将这个区间一分为二,一半满足这个性质,一半不满足这个性质,二分就可以把两个边界点找出来
比如用区间[i,j]举例
现在存在这样的一个性质使得将[i,j]这个区间划分成了两段区间[i,i + 1,i + 2,…,i + k],以及另外一个区间[i + k + 1,…,j]其中一个区间满足我们要求的性质,另外一个区间不能满要求的性质,那么二分就可以找出i + k 和 i + k + 1这两个值
二分左边界点的模版
while(l < r) {
int mid = l + r + 1 >> 1;
if(check(mid)) // 如果mid满足左半边的性质,那么左边界点 只能在 [mid,r]这个区间里面
l = mid;
else // 如果mid不满足左半边的性质,那么左边界点,只能在[l, mid - 1] 这个区间里面
r = mid - 1;
}
二分右边界点的模版
while(l < r) {
int mid = l + r >> 1;
if(check(mid)) // 如果mid满足右半边的性质,那么右边界点 只能在 [l,mid]这个区间里面
r = mid;
else // 如果mid不满足右半边的性质,那么右边界点,只能在[mid + 1, r] 这个区间里面
l = mid + 1;
}
二分解题的具体步骤
(待补充)
二分的注意点 (待补充)
- leetcode 35:注意l 与 r 的初始值
- leetcode 69
- leetcode 704