高效查找两个有序数组的中位数 - C++实现与解析

高效查找两个有序数组的中位数 - C++实现与解析

给定两个有序整数数组，长度均为 n，如何找到这两个数组的中位数？

例如：

输入描述 a:[1,3,5] b:[2,4,6] 输出描述: 3.5

以下是用 C++ 语言实现的代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size() + nums2.size();
    vector<int> merged(n);
    merge(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), merged.begin());
    if (n % 2 == 0) {
        return (merged[n / 2 - 1] + merged[n / 2]) / 2.0;
    } else {
        return merged[n / 2];
    }
}

int main() {
    vector<int> nums1 = {1, 3, 5};
    vector<int> nums2 = {2, 4, 6};
    
    double median = findMedianSortedArrays(nums1, nums2);
    cout << median << endl;
    
    return 0;
}

在这个示例中，我们首先将两个有序数组合并到一个新的数组中，通过使用 merge 函数来实现。merge 函数会将两个有序的输入范围合并到输出中。

然后，我们根据新数组的长度来确定中位数的位置。如果长度是偶数，中位数是位于数组中间两个数的平均值；如果长度是奇数，中位数是位于数组中间的数。

在输入的示例中，输出为 3.5，即两个有序数组的中位数。

时间复杂度分析:

此解决方案的时间复杂度为 O(n)，其中 n 是两个有序数组的长度之和，因为我们需要遍历一遍所有元素来合并数组。

更高效的解决方案:

更高效的解决方案可以使用二分查找算法，将时间复杂度降低到 O(log n)。二分查找的思路是利用数组的有序性，每次比较两个数组的中间元素，逐步缩小搜索范围，最终找到中位数。 虽然代码更复杂，但能显著提高效率，尤其是在处理大规模数组时。