Leetcode 刷题记录 15 —— 二分查找

本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答，01~07为C++语言，08及以后为Java语言。

01 搜索插入位置

class Solution {
    public int searchInsert(int[] nums, int target) {
       int left = 0;
       int right = nums.length - 1;
       while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
       }
       return left;
    }
}

02 搜索二维矩阵

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        //思路：将二维数组展开为一维数组
        int row = matrix.length;
        int column = matrix[0].length;
        int left = 0;
        int right = row * column - 1;

        while(left <= right){
            int mid = (left + right) / 2;
            int x = matrix[mid / column][mid % column];
            if(x == target){
                return true;
            }else if(x < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return false;
    }
}

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

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] positions = new int[]{-1, -1};
        int left1 = 0, left2 = 0;
        int right1 = nums.length-1, right2 = nums.length-1;

        //寻找第一个等于target的位置
        while(left1 <= right1){
            int mid1 = (left1 + right1) / 2;
            if(nums[mid1] == target){
                positions[0] = mid1;
                right1 = mid1 - 1; //重点
            }else if(nums[mid1] < target){
                left1 = mid1 + 1;
            }else{
                right1 = mid1 - 1;
            }
        }

        //寻找最后一个等于target的位置
        while(left2 <= right2){
            int mid2 = (left2 + right2) / 2;
            if(nums[mid2] == target){
                positions[1] = mid2;
                left2 = mid2 + 1; //重点
            }else if(nums[mid2] < target){
                left2 = mid2 + 1;
            }else{
                right2 = mid2 - 1;
            }
        }

        return positions;
    }
}

第一个重点确保了即使找到目标值，也会继续向左搜索，以确保找到第一个出现的索引。

第二个重点确保了即使找到目标值，也会继续向右搜索，以确保找到最后一个出现的索引。

04 搜索旋转排序数组 ⭐

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;

        //特殊情况判断
        if(n == 0){
            return -1;
        }
        if(n == 1){
            return nums[0] == target ? 0 : -1;
        }

        int left = 0;
        int right = n - 1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[0] <= nums[mid]){ //大山峰、小山峰
                if(nums[0] <= target && target < nums[mid]){
                    right = mid - 1;
                }else{
                    left = mid + 1;
                }
            }else{ //小山峰、大山峰
                if(nums[mid] < target && target <= nums[n - 1]){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}

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

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;

        //特殊情况判断
        if(n == 1){
            return nums[0];
        }

        int left = 0;
        int right = n - 1;
        int flag = nums[0];
        while(left <= right){
            int mid = (left + right) / 2;
            flag = nums[mid] < flag ? nums[mid] : flag;
            if(nums[0] <= nums[mid]){ //大山峰、小山峰
                left = mid + 1;
            }else{ //小山峰、大山峰
                right = mid - 1;
            }
        }
        return flag;
    }
}

06 寻找两个正序数组的中位数

如果对时间复杂度的要求有log，通常都需要用到二分查找。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int numsLength = m + n;

        if(numsLength % 2 == 1){
            int mid = numsLength / 2 + 1;
            double ans = myFunction(nums1, nums2, mid); //寻找第k小的数
            return ans;
        }else{
            int mid1 = numsLength / 2;
            int mid2 = numsLength / 2 + 1;
            double ans = (myFunction(nums1, nums2, mid1) + myFunction(nums1, nums2, mid2)) / 2.0;
            return ans;
        }
    }

    public int myFunction(int[] nums1, int[] nums2, int k){
        int m = nums1.length, n = nums2.length;
        int index1 = 0, index2 = 0;
        
        while(true){
            //特殊情况判断
            if(index1 == m){
                return nums2[index2 + k - 1];
            }
            if(index2 == n){
                return nums1[index1 + k - 1];
            }
            if(k == 1){
                return Math.min(nums1[index1], nums2[index2]);
            }
            
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, m) - 1;
            int newIndex2 = Math.min(index2 + half, n) - 1;
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];

            //重点
            if(pivot1 <= pivot2){
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            }else{
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}