目录
LeetCode 9 二分查找专题
房顶上的铝皮水塔
2022年01月25日 11:44
收录于文集
共14篇

参考内容：二分查找​

二分查找其实是一个非常不好写的问题。虽然二分查找的思想非常简单，但是实际操作起来的时候需要考虑一些边界情况，导致常常不能one pass。

所以我专门结合b站的这个视频中提出的模板结合Leetcode题目展开了专题练习

二分查找​

写了这些题目：

搜索插入位置，寻找峰值，在排序数组中查找元素的第一个位置和最后一个位置，搜索二维矩阵，搜索二维矩阵II，寻找重复数，较小的三数之和，最接近的二叉搜索树，寻找右区间来巩固我对于二叉查找的模板的理解。 

下面我首先将视频中的要点进行整理，然后逐题进行复盘。

二分查找模板 + 细节问题的数学证明 &搜索插入位置

和我们一般见到的二分查找的模板有如下几点不同：

1. left表示当前指向的元素，及其左边的元素都属于蓝色部分，right表示当前指向的元素及其右边的元素的都属于红色部分

初始化left = 1，right = N，即数组长度。之所以要如此初始化，是为了符合模板中对于left和right的定义。

2. left和right每次最后都被赋值为mid。这是因为将left = mid + 1或者是将 right = mid + 1，我们不容易判断更新之后的left是属于红色还是蓝色。

以上两点是最显著的区别，其余的数学证明大家可以参考一下原视频。

当循环结束时，left和right会终止在各自的颜色的位置，如图所示：

因此，当前最要紧的问题就是如何定义

相当于说是，只需要考虑什么元素需要加入蓝色部分，其他的元素全部都加入红色部分即可。

对于这个问题的说明 我们就使用搜索插入位置这道题来举例：

通过观察实例输入和输出，我们可以发现，最终的结果表示的下标包括了大于等于target的数字。因此我们可以将isBlue定义为小于nums的数字，代码如下：

代码块
JavaScript
自动换行
复制代码
public class 搜索插入位置_new {     class Solution {         public int searchInsert(int[] nums, int target) {             int index = bin(nums, -1, nums.length, target);             return index;         }         private int bin(int[]nums, int left, int right, int target) {             while(left + 1 != right) {                 int mid = left + ((right - left) >> 1);                 if (nums[mid] < target) left = mid;                 else right = mid;             }             // left 包括自身及其左边的值都比它小             // right 及其右边的值都大于等于自身             return right;         }     } }
复制成功

寻找峰值

关于这道题，首先需要考虑是否能使用二分查找？

首先我们假设数组中存在峰值，如果一个下标i对应的元素及其左右元素满足如下关系：

num[i] < nums[i+1] && nums[i]  > nums[i-1] 说明峰值在其右边；

num[i] > nums[i+1] && nums[i] < nums[i-1] 说明峰值在其左边；

num[i] < nums[i+1] && nums[i]   < nums[i-1] 说明在谷底，下一步往左边和右边都可以

所以可以认为使用二分查找，一次可以忽略左边或者右边的数字，加快搜索

为什么存在峰值

首先，示例以及题目中没有说明不存在峰值应该返回什么元素，所以一定存在。其实也可推导。

假设数组中存在一个元素，这个元素就是峰值；

假设数组中存在两个元素，若左边的元素大于右边的元素，左边的元素就是峰值；反之则右边的元素是峰值。存在更多元素的情况就是两个元素的情况的展开

既然如此，我们需要考虑isBlue的实现。

对于一个元素，如果这个元素小于右边大于左边，则可以放到蓝色区域，那么，最后一个放入蓝色区域的元素的下一个元素就是峰值。

代码块
JavaScript
自动换行
复制代码
public class 寻找峰值_new {
    static class Solution {
        public int findPeakElement(int[] nums) {
            if (nums.length == 1) return 0;
            return bin(nums, -1, nums.length);
        }

        // 数组中一定存在峰值吗?
        private int bin(int[]nums, int left, int right) {
            while(left + 1 != right) {
                int mid = left + ((right - left) >> 1);
                int lvalue = mid - 1 < 0 ? Integer.MIN_VALUE : nums[mid - 1];
                int rvalue = mid + 1 >= nums.length ? Integer.MIN_VALUE : nums[mid + 1];

                if (lvalue <= nums[mid] && nums[mid] <= rvalue)
                    left = mid;
                else
                    right = mid;
            }
            return right;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,1,3,5,6,4};
        System.out.println(solution.findPeakElement(nums));
    }
}
复制成功

另外题目中还说明了，不存在重复元素的情况，上述代码中等号可以去掉。

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

这题思路没有特别之处，将小于target的值归到蓝色区间，返回最后的right就可以。二分查找的模板存在一个问题，如果数组元素值都小于target，那么right的值为N；如果数组元素的值都大于target，返回值为0。

在上面的例子中，因为要找到具体的元素的下标，所以需要检查最后返回right对应的元素是不是Target，并且还需要先考虑返回的right有没有数组越界。    

代码块
JavaScript
自动换行
复制代码
class Solution {
        public int[] searchRange(int[] nums, int target) {
            int left = -1 , right = nums.length;
            while(left + 1 != right) {
                int mid = left + ((right - left) >> 1);
                // 小于target都归到蓝色区间
                if (nums[mid] < target) 
                    left = mid;
                else
                    right = mid;
            }
            // right的值就是target
            // CASE#1 有可能当前的值并不是target的值
            if (right == nums.length || nums[right] != target)
                return new int[]{-1,-1};
            int end = right;
            while (end + 1 < nums.length && nums[end + 1] == target) end ++;
            return new int[]{right, end};
        }
    }
复制成功

搜索二维矩阵

根据题意不难理解，这题就是将一个很长的数组切成一些小段放到二维数组中。其实也是按照一位数组的模板来做就完事了。m*n就是数组总长度，m*n / n表示i m*n%n 表示j：

代码块
JavaScript
自动换行
复制代码
class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length, n = matrix[0].length;
            if (matrix[m-1][n-1] < target) return false;
            int left = -1, right = m*n;
            while(left + 1 != right) {
                int mid = (left + right) >> 1;
                int i = mid / n;
                int j = mid % n;
                if (matrix[i][j] < target) left = mid;
                else right = mid;
            }
            // 最后的结果是right
            return matrix[right/n][right%n] == target;
        }
    }
复制成功

搜索二维矩阵II

这道题和上面的有所区别，因为每一行的最后一个元素不一定小于下一行的第一个元素，所以不能展开成一个长一位数组。但是这种矩阵有一种特性，从右上角开始，向左边走的元素小于他，下面的元素大于他。这样满足一种二分特性。

对于Target=5而言，因为15 大于 5，向左走；11 大于5向左，7大于5向左；4小于5 向下找到了；如果没找到就回走到数组矩阵外面，返回false即可。

这道题划分红蓝区间不容易设计，直接使用最简单的即可。

代码块
JavaScript
自动换行
复制代码
class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            int m = matrix.length, n = matrix[0].length;
            int i = 0, j = n - 1;
            while(i < m && j >= 0 ) {
                if (matrix[i][j] > target) j --;
                else if (matrix[i][j] < target) i ++;
                else // 相等情况
                    return true;
            }
            return false;
        }
    }
复制成功

较小的三数之和

题目要求找到三个数，并且让这三个数之和小于target。我们可以将原数组进行排序，找到其中的两个数，他们的下标分别记作i,j，然后找一个下标为k的数，满足nums[k] < target-nums[i]-nums[j]，如图所示，蓝色的部分就是找到的区间.

通过图我们可以发现，其实也不会出现重复的问题。比如当j指向下标为2的元素，也就是1时，k也找不到下标为3的元素，也就是3.

具体代码如下：

代码块
clike
自动换行
复制代码
class Solution {
        public int threeSumSmaller(int[] nums, int target) {
            Arrays.sort(nums); // 排序
            int n = nums.length, cnt = 0;
            for(int i = 0; i + 2 < n; i ++) {
                for (int j = i + 1; j + 1 < n ; j++) {
                    // 二分查找具体的值
                    int real = target - nums[i] - nums[j];
                    int index = bin(nums, j, n, real);
                    cnt += index - j;
                }
            }

            return cnt;
        }

        // 找到一个值小于2
        private int bin(int[]nums, int left, int right, int target) {
            while(left + 1 != right) {
                int mid = left + ((right - left)>>1);
                if (nums[mid] < target) left = mid;
                else right = mid;
            }
            return left;
        }
    }
复制成功

寻找右区间

这道题要求找当前的区间的右区间，如果找不到就-1，找得到就下标。    其实做了这么多关于区间的题，不论是使用贪心的原则，合并区间也好，还是其他的方法也罢，一上来的第一个思路就是将区间元素按照区间中的start大小进行排序。我们想想这个排序的思路是否可以运用到这道题。

对于图中的这个例子而言，因为end一定大于start，通过start进行排序之后的元组可以通过检查当前mid指向的元素是否为[1,4]的右区间。我们通过设计不是右区间的在蓝色区域，第一个是右区间的在红色区域就满足了题目的最小化start的要求。

同时这道题其实有个case很智障，[1,1]也是自己的右区间，所以需要额外判断当start=end的情况。

具体代码如下：

代码块
clike
自动换行
复制代码
class Solution {
        public int[] findRightInterval(int[][] intervals) {
            // 在排序之前使用Hash表记录int[] 的下标
            int n = intervals.length;
            HashMap<int[], Integer> map = new HashMap<>();
            for (int i = 0; i < n; i++)
                map.put(intervals[i], i);

            // 将数组进行排序
            Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));

            int[] ans = new int[n];
            for (int i = 0; i < n; i++) {
                // right 包括 （right）以后的数组的第一个元素都是大于等于 target
                int[] cur = intervals[i];
                int oriIndex = map.get(intervals[i]); // before sorting
                if (cur[0] == cur[1]) {
                    ans[oriIndex] = oriIndex;
                    continue;
                }
                int index = bin(i, n, intervals, cur[1]);
                    // 在数组中可能二分查找找到不到这个元素
                if (index >= n || intervals[index][0] < cur[1])
                    ans[oriIndex] = -1;
                else
                    ans[oriIndex] = map.get(intervals[index]);
            }
            return ans;
        }

        // 搜索使用[left, right]下标框定起来的闭区间
        private int bin(int left, int right, int[][] nums, int target) {
            while (left + 1 != right) {
                // 相等的并入右区间
                int mid = left + ((right - left) >> 1);
                if (nums[mid][0] < target) left = mid;
                else right = mid;
            }
            return right;
        }
    }
复制成功

通过我们的整理我们可以看到，视频中的这个模板非常适合完成对于给定的数组搜索其中元素的任务，但是对于没有给定数组的情况，或者不容易构造数组的情况，下面还有一些通用的技巧：

寻找重复数

这道题中，给出长度为n+1的数组，但是数组中有一个存在元素i，i属于[1,n]存在一个重复值。我们可以有这样的一个思路，我们设计left,right和mid指针，我们在题目给定nums数组中，猜[left,mid]框定的区间内，nums中的元素出现的次数。如果在nums中出现的次数大于mid-left+1，即区间长度，说明存在重复元素。如果没有出现重复元素说明当前[left,mid]区间不对，我们转到[mid+1,right]子区间中尝试。

具体代码如下：

代码块
clike
自动换行
复制代码
class Solution {
        public int findDuplicate(int[] nums) {
            // 遍历 left 和 right区间内的所有数字
            // 只存在一个重复数字
            int left = 1 , right = nums.length - 1;
            while(left < right) {
                int mid = left + ((right - left) >> 1);
                // 统[left: mid]区间的数字的数量
                int cnt = 0;
                for (int num : nums) {
                    if (num <= mid && num >= left)
                        cnt++;
                }
                // 如果当前区间的数字的数量超出
                // 区间确定的数字和统计的数量的关系只有两种，要么是小于cnt要么是等于cnt
                // 而且最后left == right时退出，所以返回left是可以的
                if (mid - left + 1 < cnt)
                    right = mid;
                else
                    left = mid + 1;
            }
            return left;
        }
    }
复制成功

此外，如果要验证自己的代码是否正确可以使用最基本的一些Case进行尝试：

  1. 数组长度为2时数组为{1,1}，返回left会返回1

  2. 数组长度为3时，排序后的数组可能为{1,1,2}或者是{1,2,2}，left=1，right=2，第一次的mid等于1。对于{1,1,2}，[1,1]区间内的cnt是2，right = mid,退出循环，left=1，并且作为返回值；对于{1,2,2},[1,1]区间的cnt为1，cnt等于区间长度，left = mid + 1，退出循环，返回left=2. 这个例子也说明当cnt等于区间长度的时候left=mid+1.

最接近的二叉搜索树

二叉搜索树可以通过成中序遍历形成一个有序数组，然后二分查找是可以的，这样时间空间复杂度都很高，没必要。

如果target小于当前的节点，那么接近这个数的节点肯定在左子树（往右边走越来越大，而且有右子树的最小值肯定大于当前节点）；反之如果大于，找右子树。终止的节点肯定在叶子节点上，同时在遍历的过程记录一个最小的距离的值。

具体代码如下：

代码块
clike
自动换行
复制代码
  class Solution {
        public int closestValue(TreeNode root, double target) {
            int val, closest = root.val;
            while (root != null) {
                val = root.val;
                closest = Math.abs(val - target) < Math.abs(closest - target) ? val : closest;
                root = target < root.val ? root.left : root.right;
            }
            return closest;
        }
    }
复制成功

二分查找 Leetcode
本文为我原创，未经授权禁止转载
cv14984337