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

本文主要是介绍【面试经典 150 | 二分查找】寻找两个正序数组的中位数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

写在前面
Tag
题目来源
题目解读
- 方法一：朴素
- 方法二：二分查找【寻找第k小元素】
写在最后

写在前面

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

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

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

Tag

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

题目来源

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

题目解读

方法一：朴素

给出两个有序数组，要求找出两个有序数组合并后数组的中位数。朴素的方法是直接拼接两个数组，然后排序，取出 “中间” 位置的元素，即为中位数。时间和空间复杂度分别为 $O ((m + n) l o g (m + n))$ 和 $O (l o g (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 (l o g (m + n))$ ， $m$ 和 $n$ 分别为数组 nums1 和 nums2 的长度。每一轮循环都会将查找缩小一半。