查看“︁09-进阶算法/04-二分查找与二分答案”︁的源代码


== 二分查找 ==

在'''有序序列'''中查找目标值，每次将搜索范围缩小一半，时间复杂度 <math>O(\log n)</math>。

=== 二分查找模板 ===

<syntaxhighlight lang="cpp">
// 在有序数组 a 中查找第一个 >= x 的位置（lower_bound）
int lower_bound(int a[], int n, int x)
{
    int l = 1, r = n, ans = n + 1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (a[mid] >= x)
        {
            ans = mid;
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }
    return ans;
}
</syntaxhighlight>

=== 查找最后一个 <= x 的位置 ===

<syntaxhighlight lang="cpp">
int upper_bound(int a[], int n, int x)
{
    int l = 1, r = n, ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (a[mid] <= x)
        {
            ans = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    return ans;
}
</syntaxhighlight>

== 二分答案 ==

当问题满足'''单调性'''时，可以对答案进行二分，验证当前答案是否可行。

=== 典型场景 ===

* 最大值最小化 / 最小值最大化
* 判断是否存在一种方案满足某个条件

=== 模板 ===

<syntaxhighlight lang="cpp">
auto check = [&](int mid) -> bool
{
    // 判断答案 mid 是否可行
    return true; // or false
};

int l = 1, r = max_value, ans = 0;
while (l <= r)
{
    int mid = (l + r) / 2;
    if (check(mid))
    {
        ans = mid;
        l = mid + 1; // 或 r = mid - 1，取决于求最大还是最小
    }
    else
    {
        r = mid - 1;
    }
}
</syntaxhighlight>

[[Category:进阶算法]]
[[Category:三三文档]]