【面试经典 150 | 二分查找】寻找两个正序数组的中位数

写在前面

本专栏专注于分析与讲解【面试经典150】算法，两到三天更新一篇文章，欢迎催更……

专栏内容以分析题目为主，并附带一些对于本题涉及到的数据结构等内容进行回顾与总结，文章结构大致如下，部分内容会有增删：

• Tag：介绍本题牵涉到的知识点、数据结构；
• 题目来源：贴上题目的链接，方便大家查找题目并完成练习；
• 题目解读：复述题目（确保自己真的理解题目意思），并强调一些题目重点信息；
• 解题思路：介绍一些解题思路，每种解题思路包括思路讲解、实现代码以及复杂度分析；
• 知识回忆：针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【数组】【二分查找】【双指针】

题目来源

4. 寻找两个正序数组的中位数

题目解读

方法一：朴素

给出两个有序数组，要求找出两个有序数组合并后数组的中位数。朴素的方法是直接拼接两个数组，然后排序，取出 “中间” 位置的元素，即为中位数。时间和空间复杂度分别为 $O((m+n)log(m+n))$ 和 $O(log(m+n)$。

如果利用 88. 合并两个有序数组 中的双指针解法合并数组，再找出 “中间” 位置，分别可以把时空复杂度降到 $O(m+n)$ 和 $O(m+n)$。

如果不执着于合并两个有序数组，可以利用双指针直接找到中位数的位置。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 000 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。（双指针直接找中位数参考自 官方题解）

这样的空间复杂度可以降到 $O(1)$，但是时间复杂度依然是 $O(m+n)$。

题目中要求对数时间的解法，通常就是二分查找了。

方法二：二分查找【寻找第k小元素】

寻找第 k 小元素

根据中位数的定义，当 m+n 是奇数时，中位数是两个有序数组中的第 (m+n)/2 个元素（计数从1开始），当 m+n 是偶数时，中位数是两个有序数组中的第 (m+n)/2 个元素和第 (m+n)/2+1 个元素的平均值。因此，这道题可以转化成寻找两个有序数组中的第 k 小的数，其中 k 为 (m+n)/2 或 (m+n)/2+1。

如何二分寻找第 k 小元素

假设两个数组分别为 A 和 B。要寻找第 k 小元素，我们可以比较 A[k / 2 - 1] 和 B[k / 2 - 1]:

• 如果 A[k / 2 - 1] < B[k / 2 - 1]，则比 A[k / 2 - 1] 小的数最多只有 A 的前 k/ 2 - 1 个数 和 B 的前 k/ 2 - 1 个数，即最多共计 k - 2 个数，那么 A[0] 到 A[k/2 - 1] 不可能是第 k 个数，可以全部排除。
• 同理， A[k / 2 - 1] > B[k / 2 - 1] 时，可以排除 B[0] 到 B[k/2 - 1]。
• 当 A[k / 2 - 1] = B[k / 2 - 1] 时，可以归入以上任意一种情况。

三种情况需要特殊处理：

• 如果 A[k/2−1] 或者 B[k/2−1] 越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少 k 的值，而不能直接将 k 减去 k/2。
• 如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k 小的元素。
• 如果 k=1，我们只要返回两个数组首元素的最小值即可。

代码

class Solution {
public:
    int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {
        int m = nums1.size(), n = nums2.size();
        int idx1 = 0, idx2 = 0; // 表示排除后新的开始位置

        while (true) {
            if (idx1 == m) {    // nums1 都被排除完
                return nums2[idx2 + k - 1];
            }
            if (idx2 == n) {    // nums2 都被排除完
                return nums1[idx1 + k - 1];
            }
            if (k == 1) {       // 找出第 1 小的元素
                return min(nums1[idx1], nums2[idx2]);
            }

            int newIdx1 = min(idx1 + k/2 - 1, m-1);
            int newIdx2 = min(idx2 + k/2 - 1, n-1);
            if (nums1[newIdx1] <= nums2[newIdx2]) {
                k -= newIdx1 - idx1 + 1;
                idx1 = newIdx1 + 1;
            }
            else {
                k -= newIdx2 - idx2 + 1;
                idx2 = newIdx2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int totalLen = nums1.size() + nums2.size();
        if (totalLen & 1) {   // 奇数
            return getKthElement(nums1, nums2, (totalLen + 1) / 2);
        }
        else {
            return (getKthElement(nums1, nums2, (totalLen + 1) / 2) + getKthElement(nums1, nums2, (totalLen + 1) / 2 + 1)) / 2.0; 
        }
    }
};

复杂度分析

时间复杂度：$O(log(m+n))$，$m$ 和 $n$ 分别为数组 nums1 和 nums2 的长度。每一轮循环都会将查找缩小一半。

空间复杂度：$O(1)$。

写在最后

如果您发现文章有任何错误或者对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法，欢迎评论区交流。

最后，感谢您的阅读，如果有所收获的话可以给我点一个 👍 哦。