二分查找应用场景:

  • 处理的问题往往具有单调性或局部单调性
  • 通过二分(分治的思想)缩小查找范围
  • 需要注意边界问题

应用场景

  • 70%的二分都是跟单调性有关,有单调性的题目一般都可以二分。
  • 95%的题目存在两段性的性质。一部分满足,一部分不满足。

算法思想

将区间分为左右两边(分治),判断中点,确定答案在哪一边,每次缩小一半,直到得到最终答案。

  • 需要注意边界问题

模板

二分模板一共有两个,分别适用于不同情况。

算法思路:假设目标值在闭区间[l, r]中, 每次将区间长度缩小一半,当l = r时,我们就找到了目标值。

版本1

当我们将区间[l, r]划分成[l, mid][mid + 1, r]时,其更新操作是r = mid或者l = mid + 1; 计算mid时不需要加1。

C++ 代码模板:

int bsearch_1(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

版本2

当我们将区间[l, r]划分成[l, mid - 1][mid, r]时,其更新操作是r = mid - 1或者l = mid; 此时为了防止死循环,计算mid时需要加1。

C++ 代码模板:

int bsearch_2(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

练习题