【LeetCode Hot100 二分查找】搜索插入位置、搜索二维矩阵、搜索旋转排序数
搜索插入位置给定一个排序数组和一个目的值，在数组中找到目的值，并返回其索引。如果目的值不存在于数组中，返回它将会被按序次插入的位置。
请必须利用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums = , target = 5
输出: 2
示例 2:
输入: nums = , 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 == target) {
return mid;
} else if (nums > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}
搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
[*]每行中的整数从左到右按非严格递增序次排列。
[*]每行的第一个整数大于前一行的末了一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
https://i-blog.csdnimg.cn/direct/47efa15c11794c51bbf6692dbaf06126.png
思绪
把该二维矩阵设想成一个一维的有序数组，那么在该一维数组的第 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.length;
int left = 0, right = m*n-1;
while(left <= right) {
int mid = left + (right - left) / 2;
int val = matrix;
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 = , target = 8
输出：
示例 2：
输入：nums = , 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 == target) {
leftBoard = mid;
right = mid - 1;// 找到之后 在 mid 的左边区间继续找，直到找到最左边的边界
} else if(nums < 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 == target) {
rightBoard = mid;
left = mid + 1;
} else if(nums < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return new int[]{leftBoard, rightBoard};
}
}
寻找旋转排序数组中的最小值
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。比方，原数组 nums = 在变化后可能得到：
若旋转 4 次，则可以得到
若旋转 7 次，则可以得到
注意，数组 , a, a, …, a] 旋转一次 的效果为数组 , a, a, a, …, a] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法办理此问题。
示例 1：
输入：nums =
输出：1
解释：原数组为 ，旋转 3 次得到输入数组。
示例 2：
输入：nums =
输出：0
解释：原数组为 ，旋转 3 次得到输入数组。
思绪
设 x=nums 是现在二分取到的数。
我们须要判定 x 和数组最小值的位置关系，谁在左边，谁在右边？
把 x 与末了一个数 nums 比巨细：
[*]如果 x>nums，那么可以推出以下结论：
[*]nums 一定被分成左右两个递增段；
[*]第一段的所有元素均大于第二段的所有元素；
[*]x 在第一段。
[*]最小值在第二段。
[*]所以 x 一定在最小值的左边。
[*]如果 x≤nums，那么 x 一定在第二段。（大概 nums 就是递增数组，此时只有一段。）
[*]x 要么是最小值，要么在最小值右边。
所以，只须要比较 x 和 nums 的巨细关系，就间接地知道了 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 > nums) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return nums;
}
}
搜索旋转排序数组
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 , nums, …, nums, nums, nums, …, nums]（下标 从 0 开始 计数）。比方， 在下标 3 处经旋转后可能变为 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目的值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法办理此问题。
示例 1：
输入：nums = , target = 0
输出：4
示例 2：
输入：nums = , target = 3
输出：-1
思绪
利用上一题的思绪，先找到该旋转排序数组的最小值的位置，然后根据 target 和 旋转的位置（旋转排序数组的末了一个数）的巨细进行比较，判定是在左边查找还是在右边查找。
代码
class Solution {
public int search(int[] nums, int target) {
int min = findMin(nums);// 先找到最小值的下标
int n = nums.length;
if (target == nums) {
return n - 1; // 相等的话直接返回
} else if (target > nums) {
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 > nums) {
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 == target) {
return mid;
} else if (nums > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
寻找两个正序数组的中位数（hard）
给定两个巨细分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = , nums2 =
输出：2.00000
解释：合并数组 = ，中位数 2
示例 2：
输入：nums1 = , nums2 =
输出：2.50000
解释：合并数组 = ，中位数 (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…nums1，右边部门是 nums1…nums1。
[*]同样地，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 <= nums2（nums1 左边的最大值小于 nums2 右边的最小值）。
[*]nums2 <= nums1（nums2 左边的最大值小于 nums1 右边的最小值）。
如果这些条件成立，说明我们找到了合适的分割位置。
[*]计算中位数
[*]如果两个数组的总长度是奇数，中位数就是左边部门的最大值，max(nums1, nums2)。
[*]如果两个数组的总长度是偶数，中位数是左边部门的最大值和右边部门的最小值的平均值：
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,nums2)+min(nums1,nums2)) / 2 median=(max(nums1,nums2)+min(nums1,nums2))/2
[*]二分查找的调解
[*]如果不满足条件，意味着 partition1 须要调解：
[*]如果 nums1 > nums2，则须要将 partition1 向左移，即减小 partition1。
[*]如果 nums2 > nums1，则须要将 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;
int minRight1 = (partition1 == n) ? Integer.MAX_VALUE : nums1;
int maxLeft2 = (partition2 == 0) ? Integer.MIN_VALUE : nums2;
int minRight2 = (partition2 == m) ? Integer.MAX_VALUE : nums2;
// 检查是否找到合适的分割位置
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;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]