两个等长有序数组并集的中位数数据结构c语言

以下是两个等长有序数组并集的中位数数据结构的C语言实现：

#include <stdio.h>

// 返回两个数中较小的一个
int min(int a, int b) {
    return a < b ? a : b;
}

// 返回两个数中较大的一个
int max(int a, int b) {
    return a > b ? a : b;
}

// 返回有序数组 nums1 和 nums2 的并集中的中位数
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    if (nums1Size > nums2Size) {
        // 保证 nums1Size <= nums2Size
        return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
    }

    int left_half = (nums1Size + nums2Size + 1) / 2; // 左半部分元素个数
    int left = 0, right = nums1Size; // 二分查找左半部分的范围 [left, right]
    while (left <= right) {
        int i = (left + right) / 2; // nums1 的左半部分的右边界
        int j = left_half - i; // nums2 的左半部分的右边界
        if (i < nums1Size && nums2[j-1] > nums1[i]) {
            // i 太小了，需要往右移动
            left = i + 1;
        } else if (i > 0 && nums1[i-1] > nums2[j]) {
            // i 太大了，需要往左移动
            right = i - 1;
        } else {
            // 找到了合适的 i 和 j
            int left_max = 0;
            if (i == 0) {
                left_max = nums2[j-1];
            } else if (j == 0) {
                left_max = nums1[i-1];
            } else {
                left_max = max(nums1[i-1], nums2[j-1]);
            }
            if ((nums1Size + nums2Size) % 2 == 1) {
                // 总元素个数为奇数
                return left_max;
            } else {
                // 总元素个数为偶数
                int right_min = 0;
                if (i == nums1Size) {
                    right_min = nums2[j];
                } else if (j == nums2Size) {
                    right_min = nums1[i];
                } else {
                    right_min = min(nums1[i], nums2[j]);
                }
                return (left_max + right_min) / 2.0;
            }
        }
    }

    return 0; // 不会执行到这里
}

int main() {
    int nums1[] = {1, 3};
    int nums1Size = sizeof(nums1) / sizeof(nums1[0]);
    int nums2[] = {2, 4, 5};
    int nums2Size = sizeof(nums2) / sizeof(nums2[0]);
    double median = findMedianSortedArrays(nums1, nums1Size, nums2, nums2Size);
    printf("Median = %f\n", median); // Median = 3.000000
    return 0;
}

以上代码使用二分查找的方法，时间复杂度为 O(log(min(m, n)))，其中 m 和 n 分别是两个有序数组的长度。