二分查找， Binary Search

二分总结 by labuladong

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