【LeetCode Hot100 二分查找】搜索插入位置、搜索二维矩阵、搜索旋转排序数组、寻找两个正序数组的中位数
二分查找
- 搜索插入位置
- 搜索二维矩阵
- 在排序数组中查找元素的第一个和最后一个位置
- 寻找旋转排序数组中的最小值
- 搜索旋转排序数组
- 寻找两个正序数组的中位数（hard）
搜索插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 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
i
i 个位置的数可以用二维矩阵 ( m 行 n 列) 表示，即在
i
/
n
i/n
i/n 行，
i
%
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
思路
我们将通过 二分查找 来解决这个问题，具体步骤如下：
- 确保 nums1 是较短的数组
- 由于我们要在较短的数组上进行二分查找，为了减少计算复杂度，我们首先确保 nums1 的长度小于或等于 nums2。如果 nums1 的长度大于 nums2，我们交换这两个数组。
- 这样做的目的是保证二分查找的次数最小化，最大化效率。
- 分割数组
- 我们的目标是将两个数组分割成左右两部分，使得合并后的两个部分的元素个数相同，或者左边多一个元素（如果总长度是奇数）。具体来说，假设 nums1 的长度是 n，nums2 的长度是 m，则：
- 左边部分的元素个数应为 (n + m + 1) / 2，这个值可以保证左边部分最多比右边部分多一个元素（当总长度是奇数时）。
- 右边部分的元素个数为 n + m - (n + m + 1) / 2。
- 二分查找
- 在 nums1 上执行二分查找，假设当前查找的分割位置是 partition1，那么 nums1 的左边部分就是 nums1[0]…nums1[partition1-1]，右边部分是 nums1[partition1]…nums1[n-1]。
- 同样地，nums2 的分割位置 partition2 可以通过以下公式计算：
p a r t i t i o n 2 = ( n + m + 1 ) / 2 − p a r t i t i o n 1 partition2= (n+m+1)/2 −partition1 partition2=(n+m+1)/2−partition1
这个公式确保了左边部分的总元素个数为 (n + m + 1) / 2。
- 确保分割符合条件
- 为了保证左边部分的所有元素都小于或等于右边部分的所有元素，我们需要检查：
- nums1[partition1 - 1] <= nums2[partition2]（nums1 左边的最大值小于 nums2 右边的最小值）。
- nums2[partition2 - 1] <= nums1[partition1]（nums2 左边的最大值小于 nums1 右边的最小值）。
如果这些条件成立，说明我们找到了合适的分割位置。
- 计算中位数
- 如果两个数组的总长度是奇数，中位数就是左边部分的最大值，max(nums1[partition1 - 1], nums2[partition2 - 1])。
- 如果两个数组的总长度是偶数，中位数是左边部分的最大值和右边部分的最小值的平均值：
m e d i a n = ( m a x ( n u m s 1 [ p a r t i t i o n 1 − 1 ] , n u m s 2 [ p a r t i t i o n 2 − 1 ] ) + m i n ( n u m s 1 [ p a r t i t i o n 1 ] , n u m s 2 [ p a r t i t i o n 2 ] ) ) / 2 median = (max(nums1[partition1−1],nums2[partition2−1])+min(nums1[partition1],nums2[partition2])) / 2 median=(max(nums1[partition1−1],nums2[partition2−1])+min(nums1[partition1],nums2[partition2]))/2
- 二分查找的调整
- 如果不满足条件，意味着 partition1 需要调整：
- 如果 nums1[partition1 - 1] > nums2[partition2]，则需要将 partition1 向左移，即减小 partition1。
- 如果 nums2[partition2 - 1] > nums1[partition1]，则需要将 partition1 向右移，即增大 partition1。
- 边界条件
- 对于数组的边界，我们使用 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;
}
}