【LeetCode Hot100 二分查找】搜索插入位置、搜索二维矩阵、搜索旋转排序数组、寻找两个正序数组的中位数

搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

代码：
闭区间解法

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

搜索二维矩阵

给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

思路
把该二维矩阵设想成一个一维的有序数组，那么在该一维数组的第 $i$ 个位置的数可以用二维矩阵 ( m 行 n 列) 表示，即在 $i/n$ 行，$i\%n$ 列.

代码
在上一题的基础上修改代码：

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

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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

思路
用两次二分查找分别找左边界和有边界
第一次二分法找左边界，第二次二分法找右边界

代码
先初始化左边界有边界为 -1

class Solution {public int[] searchRange(int[] nums, int target) {int left = 0, right = nums.length - 1;int leftBoard = -1, rightBoard = -1;// 寻找左边界while(left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {leftBoard = mid; right = mid - 1;  // 找到之后 在 mid 的左边区间继续找，直到找到最左边的边界} else if(nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}left = 0;right = nums.length - 1;// 寻找右边界while(left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {rightBoard = mid;left = mid + 1;} else if(nums[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return new int[]{leftBoard, rightBoard};}
}

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。

思路
设 x=nums[mid] 是现在二分取到的数。
我们需要判断 x 和数组最小值的位置关系，谁在左边，谁在右边？
把 x 与最后一个数 nums[n−1] 比大小：

• 如果 x>nums[n−1]，那么可以推出以下结论：
  • nums 一定被分成左右两个递增段；
  • 第一段的所有元素均大于第二段的所有元素；
  • x 在第一段。
  • 最小值在第二段。
  • 所以 x 一定在最小值的左边。
• 如果 x≤nums[n−1]，那么 x 一定在第二段。（或者 nums 就是递增数组，此时只有一段。）
  • x 要么是最小值，要么在最小值右边。

所以，只需要比较 x 和 nums[n−1] 的大小关系，就间接地知道了 x 和数组最小值的位置关系，从而不断地缩小数组最小值所在位置的范围，二分找到数组最小值。

代码

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

搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4
示例 2：
输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

思路
使用上一题的思路，先找到该旋转排序数组的最小值的位置，然后根据 target 和 旋转的位置（旋转排序数组的最后一个数）的大小进行比较，判断是在左边查找还是在右边查找。

代码

class Solution {public int search(int[] nums, int target) {int min = findMin(nums);  // 先找到最小值的下标int n = nums.length;if (target == nums[n -1]) {return n - 1;   // 相等的话直接返回} else if (target > nums[n-1]) {return searchTarget(nums, target, 0, min - 1);  // 在左边查找} else { return searchTarget(nums, target, min, n - 2);  // 在右边查找}}// 查找最小值下标public int findMin(int[] nums) {int n = nums.length;int left = 0, right = n - 2;while( left <= right) {int mid = left + (right - left) / 2;if (nums[mid] > nums[n - 1]) {left = mid + 1;} else {right = mid - 1;}}return left;}// 二分查找public int searchTarget(int[] nums, int target, int left, int right) {int n = nums.length;while(left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {right = mid - 1; } else {left = mid + 1;}}return -1;}
}

寻找两个正序数组的中位数（hard）

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

思路
我们将通过 二分查找 来解决这个问题，具体步骤如下：

1. 确保 nums1 是较短的数组

• 由于我们要在较短的数组上进行二分查找，为了减少计算复杂度，我们首先确保 nums1 的长度小于或等于 nums2。如果 nums1 的长度大于 nums2，我们交换这两个数组。
• 这样做的目的是保证二分查找的次数最小化，最大化效率。

2. 分割数组

• 我们的目标是将两个数组分割成左右两部分，使得合并后的两个部分的元素个数相同，或者左边多一个元素（如果总长度是奇数）。具体来说，假设 nums1 的长度是 n，nums2 的长度是 m，则：
  • 左边部分的元素个数应为 (n + m + 1) / 2，这个值可以保证左边部分最多比右边部分多一个元素（当总长度是奇数时）。
  • 右边部分的元素个数为 n + m - (n + m + 1) / 2。

3. 二分查找

• 在 nums1 上执行二分查找，假设当前查找的分割位置是 partition1，那么 nums1 的左边部分就是 nums1[0]…nums1[partition1-1]，右边部分是 nums1[partition1]…nums1[n-1]。
• 同样地，nums2 的分割位置 partition2 可以通过以下公式计算：
  $partition2=(n+m+1)/2-partition1$
  这个公式确保了左边部分的总元素个数为 (n + m + 1) / 2。

4. 确保分割符合条件

• 为了保证左边部分的所有元素都小于或等于右边部分的所有元素，我们需要检查：
  • nums1[partition1 - 1] <= nums2[partition2]（nums1 左边的最大值小于 nums2 右边的最小值）。
  • nums2[partition2 - 1] <= nums1[partition1]（nums2 左边的最大值小于 nums1 右边的最小值）。
    如果这些条件成立，说明我们找到了合适的分割位置。

5. 计算中位数

• 如果两个数组的总长度是奇数，中位数就是左边部分的最大值，max(nums1[partition1 - 1], nums2[partition2 - 1])。
• 如果两个数组的总长度是偶数，中位数是左边部分的最大值和右边部分的最小值的平均值：
  $median=(max(nums1[partition1-1],nums2[partition2-1])+min(nums1[partition1],nums2[partition2]))/2$

6. 二分查找的调整

• 如果不满足条件，意味着 partition1 需要调整：
  • 如果 nums1[partition1 - 1] > nums2[partition2]，则需要将 partition1 向左移，即减小 partition1。
  • 如果 nums2[partition2 - 1] > nums1[partition1]，则需要将 partition1 向右移，即增大 partition1。

7. 边界条件

• 对于数组的边界，我们使用 Integer.MIN_VALUE 和 Integer.MAX_VALUE 来处理数组分割的边界情况。例如，如果 partition1 为 0，意味着 nums1 左边部分没有元素，我们将 maxLeft1 设置为 Integer.MIN_VALUE；如果 partition1 为 n，意味着 nums1 右边部分没有元素，我们将 minRight1 设置为 Integer.MAX_VALUE。

代码

public class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 保证 nums1 是较短的数组if (nums1.length > nums2.length) {int[] temp = nums1;nums1 = nums2;nums2 = temp;}int n = nums1.length;int m = nums2.length;// 在 nums1 上进行二分查找int left = 0, right = n;while (left <= right) {int partition1 = (left + right) / 2;int partition2 = (n + m + 1) / 2 - partition1;// 获取 nums1 和 nums2 中的元素int maxLeft1 = (partition1 == 0) ? Integer.MIN_VALUE : nums1[partition1 - 1];int minRight1 = (partition1 == n) ? Integer.MAX_VALUE : nums1[partition1];int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2[partition2 - 1];int minRight2 = (partition2 == m) ? Integer.MAX_VALUE : nums2[partition2];// 检查是否找到合适的分割位置if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {// 如果数组长度是奇数if ((n + m) % 2 == 1) {return Math.max(maxLeft1, maxLeft2);} else {// 如果数组长度是偶数return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;}} else if (maxLeft1 > minRight2) {// 如果 maxLeft1 太大，调整左边界right = partition1 - 1;} else {// 如果 maxLeft2 太大，调整右边界left = partition1 + 1;}}return 0.0;}
}