基础算法3:二分法

二分法

原理介绍

二分法是一种在有序序列中快速定位元素的高效算法，时间复杂度为 O(log n)。

常规二分查找可以回答“某个值是否存在”，但更多时候我们需要知道第一个大于等于 target 的位置或第一个大于 target 的位置，这就是 STL 中 lower_bound 和 upper_bound 的功能。

• lower_bound(begin, end, target)：返回第一个 >= target 的元素的迭代器。
• upper_bound(begin, end, target)：返回第一个 > target 的元素的迭代器。

二分法中最关键的一步就是check()函数的编写，能写出check函数剩下的套模版就行了。

以下附上代码:

bool check(ll mid) {
    return mid > target;   // 条件：当前 mid 值大于目标值
}
ll l = 1, r = n;           // 假设答案的左右边界
while (l <= r) {
    ll mid = (l + r) / 2;
    if (check(mid))
        r = mid - 1;       // mid 不满足条件向左收缩
    else
        l = mid + 1;       // mid 满足条件向右收缩
}
cout << r;                 // 循环结束后，r 指向最后一个满足“<= target”的位置