二分查找

典型特征

  • 原数组是有序的, 或者改变原数组顺序不影响答案
  • 我们要找出来一个数字在数组中的位置(标准二分查找题目)

一般化特征

  • 我们能一次性排除解空间中的一半解
  • 我们要找出来解空间中的某一个解的位置

解题通法-红蓝染色法

我们能将数组依照单调性分成两部分, 以我们要找出target为例

num >= target的部分染成蓝色, num < target为红色, 我们需要染色的区间是[left, right]或者(left-1, right+1)…

  • [left, right]要染色的区间的含义就是我们现在没有染色也就是不知道其中的元素和target之间的关系

循环不变量(以两端闭区间举例)

  • left - 1始终是红色
  • right + 1始终是蓝色

思考顺序

  1. 首先确定我们怎么确定答案, 这种方式一定是要利用原数组在找到答案方面的单调性, 我们一定能一次性排除一半的解空间
  2. 确定下来红蓝染色情况
  3. 确定下来没有染色区间的开闭选择(一般是双开区间)

典型例题及实现

找到第一个大于等于target的值

闭区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int lower_bound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    // [left, right], left == right + 1 区间为空
    // left - 1始终 < target
    // right + 1始终 >= target
    while (left < right + 1) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) 
            left = mid + 1;
        else 
            right = mid - 1;
    }

    return right + 1;
}

开区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int lower_bound(int[] nums, int target) {
    int left = -1;
    int right = nums.length;

    // (left, right), left + 1 == right 区间为空
    // left 始终 < target
    // right 始终 >= target
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) 
            left = mid;
        else 
            right = mid;
    }

    return right;
}

左开右闭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int lower_bound(int[] nums, int target) {
    int left = -1;
    int right = nums.length - 1;

    // (left, right], left == right 区间为空
    // left 始终 < target
    // right + 1始终 >= target
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (nums[mid] < target) 
            left = mid;
        else 
            right = mid - 1;
    }

    return right + 1;
}

这里会有个额外的问题是mid向下取整, 会在left = -1, right = 0的时候取到-1, 所以我们需要调整成向上取整, 在left = -1, right = 0的时候取整到0, 就会不落到区间外面了

左闭右开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private int lower_bound(int[] nums, int target) {
    int left = 0;
    int right = nums.length;

    // [left, right), left == right 区间为空
    // left - 1始终 < target
    // right 始终 >= target
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) 
            left = mid + 1;
        else 
            right = mid;
    }

    return right;
}

题单

典型题目

35. 搜索插入位置

74. 搜索二维矩阵

34. 在排序数组中查找元素的第一个和最后一个位置

非典型题目

33. 搜索旋转排序数组

153. 寻找旋转排序数组中的最小值

4. 寻找两个正序数组的中位数

参考链接

灵茶山艾府-红蓝染色法