notes

Appearance

二分搜索 ​

使用步骤 ​

  1. 确定二分的范围。

    尤其要注意边界，比如所搜索的范围是否全满足或者全不满足

  2. 编写check函数。

    二分搜索最关键也是最难的部分

  3. 二分搜索确定“红蓝”区间。

    可以通过是否满足题目条件，把二分搜索的范围分为红蓝两个区间

板子 ​

c++板子

cpp
int l = -1, r = n;
while(l + 1 != r)
{
    int mid = (l + r) / 2;
    if(check(mid)) {
        l = mid;
    }else {
        r = mid;
    }
}

右边界设置为-1，左边界设置为n是为了处理全是红(蓝)区间的情况。

lower_bound 和 upper_bound ​

C++的stl中自带用二分实现的 lower_bound 查找第一个大于等于某个值和 upper_bound 查找第一个大于某个值的数，返回的皆为所找到的位置的指针（迭代器）。

示例用法：

  • 找到第一个 的元素: lower_bound(arr.begin(), arr.end(), 5)
  • 找到最后一个 的元素: lower_bound(arr.begin(), arr.end(), 5) - 1
  • 找到第一个 的元素: upper_bound(arr.begin(), arr.end(), 5)
  • 找到最后一个 的元素 upper_bound(arr.begin(), arr.end(), 5) - 1

alt text

数组默认是从小到大排列的，如需按从大到小或其它排列，可以通过第四个参数自定义。如从大到小: upper_bound(arr.begin(), arr.end(), 5, greater<int>()) 找到第一个小于5的元素