「二分」模板其实有两套,主要是根据 check(mid)
函数为 true
时,需要调整的是 l
指针还是 r
指针来判断。
当 check(mid) == true
调整的是 l
时:计算 mid
的方式应该为 mid = l + r + 1 >> 1
:
long l = 0, r = 1000009;
while (l < r) {
long mid = l + r + 1 >> 1;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
当 check(mid) == true
调整的是 r
时:计算 mid
的方式应该为 mid = l + r >> 1
:
long l = 0, r = 1000009;
while (l < r) {
long mid = l + r >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}