【面试题】【C语言】寻找两个正序数组的中位数

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

仅供学习

题目

---

算法时间复杂度

二分查找算法，时间复杂度为 O(log(min(m, n)))，其中 m 和 n 分别是两个数组的长度。

子函数

查找两个数字的最大值

int max(int a, int b) {
    return a > b ? a : b;
}
1
2
3

---

查找两个数字的最小值

int min(int a, int b) {
    return a < b ? a : b;
}
1
2
3

---

findMedianSortedArrays

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    // Ensure nums1 is the smaller array
    if (nums1Size > nums2Size) {
        return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
    }

    int x = nums1Size;
    int y = nums2Size;
    int low = 0;
    int high = x;

    while (low <= high) {
        int partitionX = (low + high) / 2;
        int partitionY = (x + y + 1) / 2 - partitionX;

        int maxX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1];
        int minX = (partitionX == x) ? INT_MAX : nums1[partitionX];

        int maxY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1];
        int minY = (partitionY == y) ? INT_MAX : nums2[partitionY];

        if (maxX <= minY && maxY <= minX) {
            // We have partitioned array at the correct place
            // Now we get max of left elements and min of right elements to get the median in case of even length combined array size
            if ((x + y) % 2 == 0) {
                return ((double)max(maxX, maxY) + min(minX, minY)) / 2;
            } else {
                return (double)max(maxX, maxY);
            }
        } else if (maxX > minY) { // we are too far on the right side for partitionX. Go on left side.
            high = partitionX - 1;
        } else { // we are too far on the left side for partitionX. Go on right side.
            low = partitionX + 1;
        }
    }

    // If we reach here, it means the arrays are not sorted
    fprintf(stderr, "Input arrays are not sorted or there is some other error.\n");
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

说明

• 该代码实现了一个查找两个正序数组中位数的算法，使用了二分查找法来优化时间复杂度。
• findMedianSortedArrays 函数首先确保第一个数组（nums1）是较小的一个，这样可以减小搜索范围。
• 在 while 循环中，通过二分查找确定两个数组的分割点，使得分割后的左半部分和右半部分元素数量接近。
• 根据分割点计算最大左边元素和最小右边元素，进而确定中位数。
• 主函数通过示例数据验证了算法的正确性。