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