给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你用C语言算法找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。

### 寻找两个有序数组的中位数 要实现一个时间复杂度为 \( O(\log(m+n)) \) 的 C 语言算法来计算两个已排序数组 `nums1` 和 `nums2` 的中位数，可以采用二分查找的思想。以下是详细的解决方案： #### 算法思路 为了满足 \( O(\log(m+n)) \) 的时间复杂度需求，可以通过二分查找的方式，在较短的数组上进行操作，从而减少不必要的比较次数。具体来说，通过分割两个数组并将它们组合成一个新的虚拟数组，使得左侧部分小于右侧部分，并调整分割点直到达到平衡状态。 核心逻辑如下： - 假设较小的数组长度为 \( m \)，较大的数组长度为 \( n \)。 - 使用二分查找方法在较小的数组上寻找合适的切割点。 - 利用该切割点推导另一个数组上的对应切割点。 - 验证当前切割是否合理（即左边的最大值应小于右边的最小值），如果不合理则继续调整。 最终得到的结果取决于总元素数量是奇数还是偶数： - 如果总数为奇数，则取中间的一个值作为中位数； - 如果总数为偶数，则取中间两数值的平均值作为中位数。 #### 实现代码 下面是基于上述思想编写的 C 语言程序： ```c #include <stdio.h> #include <limits.h> double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) { if (nums1Size > nums2Size) { // Ensure nums1 is the smaller array. return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size); } int low = 0; int high = nums1Size; while (low <= high) { int partitionX = (low + high) / 2; int partitionY = ((nums1Size + nums2Size + 1) / 2) - partitionX; int maxLeftX = (partitionX == 0) ? INT_MIN : nums1[partitionX - 1]; int minRightX = (partitionX == nums1Size) ? INT_MAX : nums1[partitionX]; int maxLeftY = (partitionY == 0) ? INT_MIN : nums2[partitionY - 1]; int minRightY = (partitionY == nums2Size) ? INT_MAX : nums2[partitionY]; if (maxLeftX <= minRightY && maxLeftY <= minRightX) { if ((nums1Size + nums2Size) % 2 == 0) { double median = (fmax(maxLeftX, maxLeftY) + fmin(minRightX, minRightY)) / 2.0; return median; } else { return fmax(maxLeftX, maxLeftY); } } else if (maxLeftX > minRightY) { high = partitionX - 1; } else { low = partitionX + 1; } } return 0.0; // This line will never be reached if inputs are valid. } ``` 此函数实现了所需的 \( O(\log(m+n)) \) 时间复杂度[^1]。 #### 测试案例 下面是一个简单的测试例子用于验证上面的函数： ```c int main() { int nums1[] = {1, 3}; int nums2[] = {2}; int size1 = sizeof(nums1)/sizeof(nums1[0]); int size2 = sizeof(nums2)/sizeof(nums2[0]); printf("The median is %.1lf\n", findMedianSortedArrays(nums1, size1, nums2, size2)); return 0; } ``` 运行以上代码会输出中位数结果为 `2.0`。 --- ###