二分查找----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]  nums2.length) { int[] temp = nums1; nums1 = nums2; nums2 = temp; } int m = nums1.length, n = nums2.length; //双指针置于nums1有效部分两端 int left = 0, right = m; while(left >> 1; //左半区元素总数 i + j int 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]; //左半区完全在nums2 int nums1Right = (i == m) ? Integer.MAX_VALUE : nums1[i]; //nums1全部需要 int nums2Left = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1]; //左半区完全在nums1 int nums2Right = (j == n) ? Integer.MAX_VALUE : nums2[j]; //nums2全部需要 //分割合法性 /** 需进行边界处理,不可直接判断 if(nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]) { */ if(nums1Left <= nums2Right && nums2Left  nums2Right) { //nums1选取元素数过大  right = i - 1; //减少nums1可选元素 }  else if(nums2Left > nums1Right) { //nums2选取元素数过大  left = i + 1; //增多nums1可选元素、即减少nums2可选元素 (总数固定,此消彼长) } } } return -1; } }