【重点!!!】【二分查找】4.寻找两个正序数组的中位数

Allenlzcoder

已于 2025-06-06 01:22:16 修改

阅读量462

点赞数 10

CC 4.0 BY-SA版权

分类专栏：力扣Top100 文章标签：二分查找寻找两个正序数组的中位数

于 2023-12-24 15:34:19 首次发布

本文链接：https://blog.csdn.net/Allenlzcoder/article/details/135182491

力扣Top100 专栏收录该内容

100 篇文章

订阅专栏

文章介绍了如何使用二分查找算法在两个已排序数组中找到合并后的中位数，时间复杂度为O(log(min(m,n)))，空间复杂度为O(1)。详细描述了一个名为Solution的类中的findMedianSortedArrays方法实现过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

最佳解法：二分查找

在这里插入图片描述

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        imin, imax, half = 0, m, (m+n+1) // 2
        while imin <= imax:
            i = (imin + imax) // 2 # nums1分割线左侧元素数量
            j = half - i           # nums2分割线左侧元素数量
            if i < m and nums2[j-1] > nums1[i]: # i太小, 需要增大
                imin += 1
            elif i > 0 and nums1[i-1] > nums2[j]: # i太大，需要降低
                imax -= 1
            else:
                nums1_left_max = -inf if i == 0 else nums1[i-1]
                nums1_right_min = inf if i == m else nums1[i]
                nums2_left_max = -inf if j == 0 else nums2[j-1]
                nums2_right_min = inf if j == n else nums2[j]
                if (m + n) % 2 == 1:
                    return max(nums1_left_max, nums2_left_max)
                else:
                    return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2.0

法1：二分查找（最优解法）

时间复杂度：O(logMin(m, n))，空间复杂度：O(1)。
同时看这两种解法及其注释！！！
视频讲解：https://www.bilibili.com/video/BV1Xv411z76J/?spm_id_from=333.337.search-card.all.click&vd_source=af30aa36f473ad5a8ffdcc06e213d1f6
在这里插入图片描述

Python

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        m, n = len(nums1), len(nums2)
        total = (m + n + 1) // 2
        # 在nums1的区间[0, m]里查找恰当的分割线
        # 使得nums1[i - 1] ≤ nums2[j] && nums2[j - 1] ≤ nums1[i]
        left, right = 0, m # [a, b)开闭区间
        while left < right:
            nums1_left = (left + right + 1) // 2        # nums1分割线左边元素数量
            nums2_left = total - nums1_left             # nums2分割线左边元素数量
            if nums1[nums1_left-1] > nums2[nums2_left]: # 分割线太靠右了,需要往左移动
                right = nums1_left-1
            else:
                left = nums1_left
        i, j = left, total - left
        nums1_left_max = -inf if i == 0 else nums1[i-1]
        nums1_right_min = inf if i == m else nums1[i]
        nums2_left_max = -inf if j == 0 else nums2[j-1]
        nums2_right_min = inf if j == n else nums2[j]
        if (m + n) % 2 == 1:
            return max(nums1_left_max, nums2_left_max)
        else:
            return (max(nums1_left_max, nums2_left_max) + min(nums1_right_min, nums2_right_min)) / 2.0

Java

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
        }
        int m = nums1.length, n = nums2.length;
        // 在nums1的区间[0, m]里查找恰当的分割线
        // 使得nums1[i - 1] ≤ nums2[j] && nums2[j - 1] ≤ nums1[i]

        int totalLeft = (m + n + 1) / 2; // 左 ≥ 右
        int left = 0, right = m; // [left, right)是闭开区间
        while (left < right) {
            int nums1Left = (left + right + 1) / 2; // 是指的nums1分割线左侧元素个数(左 ≥ 右), 对应索引是nums1Left - 1
            int nums2Left = totalLeft - nums1Left;  // 是指的nums2分割线左侧元素个数(左 ≥ 右), 对应索引是nums2Left - 1
            if (nums1[nums1Left - 1] > nums2[nums2Left]) { // nums1的分割线太靠右，需要往左移
                right = nums1Left - 1; // right是取不到的边界, 下次迭代索引nums1Left - 1肯定取不到，故设置right = nums1Left - 1
            } else { // 这里并未直接判断nums2[nums2Left - 1]与nums1[nums1Left]的关系, 故使得nums1[nums1Left]尽量大
                left = nums1Left;      // left是可取到的边界,  下次迭代索引可能取到nums1Left，故设置left = nums1Left
            }
        }
        int i = left, j = totalLeft - left;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = i == m ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
        int leftMax = Math.max(nums1LeftMax, nums2LeftMax);
        int rightMin = Math.min(nums1RightMin, nums2RightMin);
        if ((m + n) % 2 == 1) {
            return (double) leftMax;
        } else {
            return ((double) leftMax + (double) rightMin) / 2.0;
        }
    }
}