二分查找

---

35. 搜索插入位置

// 二分即可，考虑最后边界情况l, r重叠也是返回l即可
class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}

74. 搜索二维矩阵

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int n = matrix[0].length;
        int i = 0, j = matrix.length * n - 1, mid;
        while (i <= j) {
            mid = (i + j) / 2;
            if (matrix[mid / n][mid % n] < target) {
                i = mid + 1;
            } else if (matrix[mid / n][mid % n] > target) {
                j = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
}

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

// 题解来自宫水三叶
// 压缩边界到某一边而不是在相等时返回
// 因此对于开区间那边，由于取不到mid,赋值为mid，还在范围内不会丢失，被开区间括号保护着
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[] { -1, -1 };
        if (nums.length == 0) {
            return ans;
        }
        ans[0] = findLeftIdx(nums, target);
        ans[1] = findRightIdx(nums, target);
        return ans;
    }

    public int findLeftIdx(int[] nums, int target) {
        int l = 0, r = nums.length - 1, mid;
        while (l < r) {
            mid = l + r >> 1; // mid靠近左边
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[l] == target ? l : -1;
    }

    public int findRightIdx(int[] nums, int target) {
        int l = 0, r = nums.length - 1, mid;
        while (l < r) {
            mid = l + r + 1 >> 1; // 通过加1使得mid靠近右边
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid;
            }
        }
        return nums[l] == target ? l : -1;
    }
}

33. 搜索旋转排序数组

// 直接官解，不太好想出来，根据中间值与nums[0]确定mid处于第一段还是第二段，只与nums[0]比较
// 如果在第一段，表示第一段升序，第一段从[0-mid)判断target是否在其中，缩小范围
// 如果在第二段，表示第二段升序，第二段从[mid,n)判断target是否在其中，缩小范围
class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1, mid;
        while (l <= r) {
            mid = (l + r) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else {
                if (nums[mid] < target && target <= nums[nums.length - 1]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
}

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

// 二分查找其中的最小值，如果mid的值比右边界的大，说明mid在第一段
// 如果小于有边界，由于右边开区间，可以令r = mid进行保护，最后还是移动l
class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1, mid;
        if (nums[0] < nums[r]) {
            return nums[0];
        }
        while (l < r) {
            mid = l + r >> 1;
            if (nums[mid] > nums[r]) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return nums[l];
    }
}