二分查找， Binary Search

二分总结 by labuladong

二分总结 by 0x3f

解析

二分查找问题可以简单归纳为：

三个模板 + 四种题型

三个模板：闭区间，左开右闭（反之同理），开区间

关键在于：循环不变量。

这里引用灵神的讲解，加入自己的理解

二分_eg_1

二分_eg_2

二分_eg_3

这个图怎么看？

  • 要确定循环中定义/不变的是什么
  • 循环中：left <= right 中 (为什么 left <= right? -> 「区间不为空」)
    • mid = (L + R) / 2
    • 判断mid
      • 如果mid >= target
        • 此时需要移动right
          • 由于我们定义为「闭区间」
            • [mid, old_right] -> 全部都只能是 >= target
          • 因此 new_right = mid - 1
          • 可以说明 [L, mid] 都是 < target 吗？
            • 不能，因为这一部分仍未探索，
      • 如果mid < target
        • 此时需要移动left
          • 由于我们定义为「闭区间」
            • [old_left, mid] -> 全部都只能是 < target
          • 因此 new_left = mid + 1

四种题型

基本可以分为

>= x lower bound

> x 也就是 >= （x + 1）

< x 也就是 (>= x) - 1

<= x 也就是 (> x) - 1也就是 >= (x + 1) - 1

（ -1 指的是左边一个）

Lowerbound, UpperBound

lower_bound：返回第一个 ≥ target 的下标

upper_bound：返回第一个 > target 的下标

  • lower_bound：判断写成 if a[mid] < t: left = mid+1 else: right = mid-1
    • 返回 left = 第一个 ≥ t
    • 不变式：i < left → a[i] < t；i > right → a[i] ≥ t
  • upper_bound：判断写成 if a[mid] <= t: left = mid+1 else: right = mid-1
    • 返回 left = 第一个 > t
    • 最后一个 ≤ t = left - 1`

看到等号放在哪一边，就知道在“向左逼近”（找第一个）还是“向右逼近”（找最后一个）

谓词

好问题！二分里“第一个 ≥ t / 第一个 > t / 最后一个 ≤ t …”的本质，是把数组按一个单调谓词（predicate）分成“两段”——左段都为假，右段都为真。然后用二分去找最左边的真（或等价地，最右边的假）。只要谓词是单调的（形如 FFFFFTTTTT），模板就统一了。

一、统一模板（半开区间更好想）

用区间 [lo, hi)，始终保持不变量：

  • 目标：第一个使 pred(i) 为真的下标
  • 不变量：[0, lo) 全为假，[hi, n) 全为真
  • 循环：
1
2
3
4
5
6
7
8
int lo = 0, hi = n;                 // 都允许落在 [0..n]
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (pred(mid)) hi = mid;        // mid 属于“真”那一段 → 收缩右边
    else           lo = mid + 1;    // mid 属于“假”那一段 → 收缩左边
}
// 退出时 lo == hi，即“第一真”的位置（可能等于 n，表示不存在）
return lo;

于是：

  • 找第一个 ≥ t：令 pred(i) = (a[i] >= t)
  • 找第一个 > t：令 pred(i) = (a[i] > t)

两者只差在谓词里的“等号”放不放。等号放到谓词里，答案就会停在“等号那一边”的最左位置。

二、为什么返回的是 lo

因为循环保持了：

  • 左侧 [0, lo) 一直为假（肯定不是答案）

  • 右侧 [hi, n) 一直为真（都可作为答案，但我们要最左那个）

    当 lo == hi 时，这个位置既不在“全假区”里，又是“全真区”的最左端，所以它就是第一个使 pred 为真的下标。

三、常见对照表

目标 谓词 pred(i) 返回值
第一个 ≥ t（lower_bound） a[i] >= t lo
第一个 > t（upper_bound） a[i] > t lo
最后一个 ≤ t 先求 first > t upper_bound(t) - 1（注意越界）
最后一个 < t 先求 first ≥ t lower_bound(t) - 1（注意越界）

小结口诀：找“第一个 True”就用 pred(mid)? hi=mid : lo=mid+1。

想落到哪边，就把“等号”放进那个谓词里。

四、Java 代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 第一个 >= t
int lowerBound(int[] a, int t) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= t) hi = mid;
        else lo = mid + 1;
    }
    return lo; // 可能等于 a.length，表示不存在
}

// 第一个 > t
int upperBound(int[] a, int t) {
    int lo = 0, hi = a.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > t) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

// 最后一个 <= t
int lastLE(int[] a, int t) {
    int idx = upperBound(a, t) - 1;
    return (idx >= 0 && a[idx] <= t) ? idx : -1; // -1 表示不存在
}

等价转换的合理性

我们统一把一切“位置类”查询都改写成“找一个分界点（第一真）”。

只要数组有序、谓词单调（形如 FFFFTTTT），就能用同一套“找第一个为真”的模板解决——简单、稳定、不容易越界。

  • 最后一个 ≤ t：把数组按 a[i] > t 分成 [≤ t][> t] 两段。

    分界点就是 第一个 > t（upper_bound）。左段的最后一个自然是 upper_bound(t) - 1。

    我们不直接写“最后一个 ≤ t”的二分，是因为“找第一个真”模板更统一。

  • 最后一个 < t：把数组按 a[i] ≥ t 分成 [< t][≥ t]。

    分界点是 第一个 ≥ t（lower_bound），所以答案是 lower_bound(t) - 1。

自己的总结

不要管是 T 还是 F，其实要找的是 变化点。 此时可以有第一个引起变化的点，或者是最后一个 引起变化点之前的点等等变体

如果我们要

找第一个 ≥ t

我们定义 左闭右开

如果Array[mid] >= t 此时，我们要找的 「变化点」 是可能是 mid，也可能是 mid 往左 此时 high = mid，[high, n) 全部都 >= t，所以我们在下一轮考虑时，就可以抛弃这部分。

把 hi 看成“右侧全达标区的左边界”。设为 mid 就是把这条边界拉到 mid，说的是“从 mid 起都达标”，并不要求“下一轮再检查 mid”。

如果Array[mid] < t 此时 我们要找的 「变化点」 是不在这里的，下一轮不要再考虑他，因此 low = mid + 1;

习题

704.二分查找

二分查找有两个模板：

  1. 左闭右闭

    1. leetcode 704:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      private int binarySearchCloseInterval(int[] nums, int target) {
              // 左闭右闭：我们要考虑右区间的数然后和target比较
              int left = 0, right = nums.length - 1;
              while (left <= right) {
                  int mid = (left + right) >> 1;
                  if (nums[mid] > target) {
                      // 因为接下来要继续判断 left <= right 而 right = mid 一定不为答案
                      // 但我们的定义又要求 right 是有意义的因此 right = mid - 1
                      right = mid - 1;
                  } else if (nums[mid] < target){
                      left = mid + 1;
                  } else {
                      return mid;
                  }
              }
              return -1;
          }

  2. 左闭右开

    1. leetcode 704:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      private int binarySearchOpenInterval(int[] nums, int target) {
             // 左闭右开：我们无需考虑右区间的数然后和target比较
             int left = 0, right = nums.length;
             while (left < right) {
                 int mid = (left + right) >> 1;
                 if (nums[mid] > target) {
                     // 此时 我们 用 left < right 保证在下一次不考虑right因此直接用 right = mid 即可
                     right = mid;
                 } else if (nums[mid] < target) {
                     left = mid + 1;
                 } else {
                     return mid;
                 }
             }
             return -1;
       }

    两者方法的本质上的差别是要不要考虑右区间:

    1. 若[left, right] 即 left <= right
      1. right = nums.length - 1 <- 很好理解，因为right本身在比较之中因此right = nums.length - 1
      2. right = mid - 1 <- 因为若 nums[mid] > target 也就是说 right 一定不为答案，且在while中我们会考虑right因为它不为答案我们需要考虑其之前的一个数: right = mid - 1;
    2. 若[left, right) 即 left < right:
      1. right = nums.length, 同理，因为right本身不含在我们的比较计划中，因此right = nums.length即可
      2. right = mid <- 因为若 nums[mid] > target 也就是说 right 一定不为答案，且在while中我们不会考虑right因为它不为答案我们不需要考虑其之前的一个数: right = mid;

总结

题型基本可以分成以下几种：

  1. 基本型
    1. 二分找出答案就可以，不需要过多的去考虑左端点右端点
  2. 找边界
    1. 找到最左/右边的满足条件的值
    2. 比如：[1, 2, 2, 2, 3] 找索引1或3的2

基本

默写二分即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

边界

左右边界的区别就在于在找到答案后先不返回而是继续寻找，

找左边界就不断收紧right，右边界不断收紧left

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 最后要检查 left 越界的情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}


int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 最后要检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}