二分查找

理解

来源：b站五点七边

  1. 提出一个问题：

    从一个升序序列中找到对应数字：

  2. 忘记以上问题，思考一个寻找红蓝边界的问题：

​ 当红蓝两方的元素未知时，如何找到红蓝边界？

  1. 设计红蓝指针，每次滑动到中间位置：

  2. 伪代码及示例

  3. 一些细节问题：

  • 如果l一开始初始化为0，当元素全为红色时，l一开始即为红色，错误✖️

  • 如果r一开始初始化为N - 1，当元素全为蓝色时， r一开始即为蓝色，错误✖️

  1. 第一个问题的答案：

  2. 模版

  3. 新方法应用及leetcode题目

房顶上的铝皮水塔-LeetCode 9 二分查找专题

题目

35. 搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = -1, r = nums.length;
        while(l + 1 != r) {
            int m = l + (r - l) / 2;
            if(nums[m] == target){
                return m;
            } else if(nums[m] < target){
                l = m;
            } else {
                r = m;
            } 
        }
        return r;
    }
}

162. 寻找峰值

关于这道题，首先需要考虑是否能使用二分查找？
首先我们假设数组中存在峰值，如果一个下标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] 说明在谷底，下一步往左边和右边都可以
所以可以认为使用二分查找，一次可以忽略左边或者右边的数字，加快搜索
class Solution {
    public int findPeakElement(int[] nums) {
        if (nums.length == 1) return 0;
        int left = -1, right = nums.length;

        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(nums[mid] >= lvalue && nums[mid] <= rvalue) {
                left = mid;
            }else{
                right = mid;
            }
        }
        return right;
    }
}

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

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

            if(nums[mid] < target) {
                left = mid;
            } else {
                // 找到第一个大于等于target的值
                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}; 
    }
}

74. 搜索二维矩阵

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int altitude = -1, latitude = -1;
        for(int i = 0; i < matrix.length; i++) {
            if(matrix[i][0] <= target && matrix[i][matrix[i].length - 1] >= target){
                altitude = i;
                latitude = matrix[i].length;
            }
        }
        if(altitude == -1 && latitude == -1) return false;
        int[] nums = new int[latitude];
        for(int i = 0;i < latitude; i++) {
            nums[i] = matrix[altitude][i];
        }
        int left = -1, right = nums.length;
        while(left + 1 != right) {
            int mid = left + ((right - left) >> 1);
            if(nums[mid] < target) {
                left = mid;
            }else {
                right = mid;
            }
        }
        return nums[right] == target;
    }
}

高手做法，但理解难度更高，空间复杂度更大

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