09-进阶算法/04-二分查找与二分答案

二分查找

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

二分查找模板

// 在有序数组 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;
}

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

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;
}

二分答案

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

典型场景

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

模板

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;
    }
}