二分查找----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;}  }