二分总结
- 左闭右开
- 求下界 上界用下界转化
- 左右区间的变化
重点是左右区间怎么扩张?
求第一个大于等于3的位置(蓝色右边界取不到,紫色左边界取得到)
\(a[mid]=3\),右边必定都是\(\geq3\)的,所有要把紫色最大限度扩张\(last=mid\),即更新后的\(last[last,last_0]\geq3\)
\(a[mid]=0\),左边必定是\(<3\)的,所以要最大限度扩张\(first=mid+1\),即更新后的\([first_0, first)<3\)
\(a[mid]=3\),右边必定是\(\geq3\),所以要最大限度扩张\(last=mid+1\),及更新后的\([last,last_0]\geq3\)
\([frst,last)\)为空,不满足循环条件,且\(first\)与\(last\)重合。返回任意值即可。
while(l < r) {
int mid = l + (r - l) / 2;
if (a[mid] < value)
l = mid + 1;
else
r = mid;
}