LeetCodeHot100 二分查找 35. 搜索插入位置 74. 搜索二维矩阵 34. 在排序数组中查找元素的第一个和最后一个位置 33. 搜索旋转排序数组 153. 寻找旋转排序数组中

35. 搜索插入位置
https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-liked

public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int index = left + ((right - left) >> 1);
            if (nums[index] == target){
                return index;
            }else if (target > nums[index]){
                left = index + 1;
            }else {
                right = index - 1;
            }
        }
        return left;
    }

74. 搜索二维矩阵
https://leetcode.cn/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-100-liked

public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length - 1;
        int n = matrix[0].length - 1;
        int i = 0;
        int j = n;
        while (i <= m && j >= 0){
            if (matrix[i][j] == target){
                return true;
            }else if (target > matrix[i][j]){
                i++;
            }else {
                j--;
            }
        }
        return false;
    }

总结：从右上角开始二分查找
34. 在排序数组中查找元素的第一个和最后一个位置
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked

public int[] searchRange(int[] nums, int target) {
        int i = 0;
        int j = nums.length - 1;
        int left = -1,right = -1;
        while (i <= j){
            int index = i + ((j - i) >> 1);
            if (target == nums[index]){
                left = index;
                while (left > 0 && nums[left - 1] == target){
                    left--;
                }
                right = index;
                while (right < nums.length - 1 && nums[right + 1] == target) {
                    right++;
                }
                break;
            }else if (target < nums[index]){
                j = index - 1;
            }else {
                i = index + 1;
            }
        }
        return new int[]{left,right};
    }

总结：二分查找，找到一个再扩散左右
33. 搜索旋转排序数组
https://leetcode.cn/problems/search-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked

public int search(int[] nums, int target) {
        int p = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i - 1] > nums[i]) {
                p = i;
                break;
            }
        }
        int left = 0;
        int right = p - 1;
        if (target <= nums[nums.length - 1]){
            left = p;
            right = nums.length - 1;
        }
        while (left <= right){
            int index = left + ((right - left) >> 1);
            if (target == nums[index]){
                return index;
            }else if (target < nums[index]){
                right = index - 1;
            }else {
                left = index + 1;
            }
        }
        return -1;
    }

总结：先找到这个旋转点p，再看从左侧二分查找，还是从右侧二分查找
153. 寻找旋转排序数组中的最小值
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked

public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right){
            int index = left + ((right - left) >> 1);
            if (nums[index] > nums[right]){
                left = index + 1;
            }else {
                right = index;
            }
        }
        return nums[left];
    }

总结：其实就是两个上升的序列，若index的值>right的值说明，min一定不在index以及index左侧，若index的值<right的值，说明min有可能是index以及index左侧，一定不是index右侧