二分查找----6.寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
/**
给定两个升序数组,将两数组看作整体寻找中位数;要求时间复杂度O(log (m+n)),则不能直接合并数组.
大致解法:
(暂时不考虑偶数情况)
如果数组合并,那么在nums1与nums2中必然存在两个分割点,
nums1的前i个元素与nums2的前j个元素构成合并后的左半区(包括中位数),
中位数即为nums1前i个元素与nums2前j个元素中较大的那个,且i + j = (m + n + 1) / 2(兼容奇偶)
同时满足左半区的最大值小于右半区的最小值
左半区元素个数:
i + j = (m + n + 1) / 2 ---> 左右半区元素个数相等(奇);左比右多1(偶);nums1取i个、nums2取j个
分割合法性:
左半区最大元素小于右半区最小元素
nums1[i - 1] < nums1[i] (必然满足)
nums1[i - 1] < nums2[j]
nums2[j - 1] < nums2[j] (必然满足)
nums2[j - 1] < nums1[i]
核心:
那么中位数寻找就转变为了搜寻满足条件的i或j; i + j = (m + n + 1) / 2
只需搜寻一个即可,哪个数组更短搜寻哪个即可
*/
class Solution {/**给定两个升序数组,将两数组看作整体寻找中位数;要求时间复杂度O(log (m+n)),则不能直接合并数组.大致解法:(暂时不考虑偶数情况)如果数组合并,那么在nums1与nums2中必然存在两个分割点,nums1的前i个元素与nums2的前j个元素构成合并后的左半区(包括中位数),中位数即为nums1前i个元素与nums2前j个元素中较大的那个,且i + j = (m + n + 1) / 2(兼容奇偶)同时满足左半区的最大值小于右半区的最小值左半区元素个数:i + j = (m + n + 1) / 2 ---> 左右半区元素个数相等(奇);左比右多1(偶);nums1取i个、nums2取j个分割合法性:左半区最大元素小于右半区最小元素nums1[i - 1] < nums1[i] (必然满足)nums1[i - 1] < nums2[j]nums2[j - 1] < nums2[j] (必然满足)nums2[j - 1] < nums1[i] 核心:那么中位数寻找就转变为了搜寻满足条件的i或j; i + j = (m + n + 1) / 2只需搜寻一个即可,哪个数组更短搜寻哪个即可*/public double findMedianSortedArrays(int[] nums1, int[] nums2) {//保证nums1是较短的数组if(nums1.length > nums2.length) {int[] temp = nums1;nums1 = nums2;nums2 = temp;}int m = nums1.length, n = nums2.length;//双指针置于nums1有效部分两端int left = 0, right = m; while(left <= right) {int sumLeft = (m + n + 1) >>> 1; //左半区元素总数 i + jint i = (left + right) >>> 1; //二分查找搜寻满足条件的i(nums1中选取的元素数)int j = sumLeft - i; // j(nums2中选取的元素数)//边界处理,左半区完全在nums1或左半区完全在nums2;以及nums1或nums2全部需要int nums1Left = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1]; //左半区完全在nums2int nums1Right = (i == m) ? Integer.MAX_VALUE : nums1[i]; //nums1全部需要int nums2Left = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; //左半区完全在nums1int nums2Right = (j == n) ? Integer.MAX_VALUE : nums2[j]; //nums2全部需要//分割合法性/** 需进行边界处理,不可直接判断if(nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]) {*/if(nums1Left <= nums2Right && nums2Left <= nums1Right) {if((m + n) % 2 == 1) { //奇数,返回左半区最大值即可return Math.max(nums1Left, nums2Left);} else { //偶数,分割点左侧最大值以及分割点右侧最小值的平均值return (Math.max(nums1Left,nums2Left) + Math.min(nums1Right,nums2Right)) / 2.0;}} //分割不合法,分情况进行调整else {if( nums1Left > nums2Right) { //nums1选取元素数过大right = i - 1; //减少nums1可选元素} else if(nums2Left > nums1Right) { //nums2选取元素数过大left = i + 1; //增多nums1可选元素、即减少nums2可选元素 (总数固定,此消彼长)}}}return -1;} }