请用c语言实现问题：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 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`。 --- ###

解法：二分查找 题目要求时间复杂度为 O(log(m+n))，可以考虑使用二分查找。 假设我们要在两个有序数组 nums1 和 nums2 中找到第 k 小的数，我们可以分别在 nums1 和 nums2 中查找第 k/2 小的数，设其为 mid1 和 mid2，比较这两个数的大小： - 如果 mid1 小于 mid2，则说明 nums1 中的前 k/2 个数都不是第 k 小的数，因为这些数加起来也不到 k，所以我们可以将 nums1 中的前 k/2 个数全部排除。更新 k 的值，让 k 减去 nums1 中排除的数的个数，同时让 nums1 的起始位置向后移动 k/2 个位置。 - 如果 mid1 大于 mid2，则说明 nums2 中的前 k/2 个数都不是第 k 小的数，因为这些数加起来也不到 k，所以我们可以将 nums2 中的前 k/2 个数全部排除。更新 k 的值，让 k 减去 nums2 中排除的数的个数，同时让 nums2 的起始位置向后移动 k/2 个位置。 - 如果 mid1 等于 mid2，则说明找到了第 k 小的数，直接返回 mid1 或 mid2 即可。 注意边界情况： - 当其中一个数组的起始位置超过数组长度，说明该数组已经全部排除，直接返回另一个数组的第 k 小的数。 - 如果 k=1，则两个数组中的最小值即为第一小的数，直接返回两个数组的起始位置指向的数中的最小值。 具体实现见下面的代码： double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){ int totalSize = nums1Size + nums2Size; if (totalSize % 2 == 1) { // 总数为奇数 return findKthSmallest(nums1, nums1Size, nums2, nums2Size, totalSize / 2 + 1); } else { // 总数为偶数 return (findKthSmallest(nums1, nums1Size, nums2, nums2Size, totalSize / 2) + findKthSmallest(nums1, nums1Size, nums2, nums2Size, totalSize / 2 + 1)) / 2.0; } } // 在 nums1 和 nums2 中查找第 k 小的数 int findKthSmallest(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) { if (nums1Size > nums2Size) { // 保证 nums1 的长度不大于 nums2 的长度 return findKthSmallest(nums2, nums2Size, nums1, nums1Size, k); } if (nums1Size == 0) { // nums1 数组为空 return nums2[k - 1]; } if (k == 1) { // 找第一小的数，即两个数组中的最小值 return fmin(nums1[0], nums2[0]); } int mid1 = fmin(nums1Size, k / 2); // 在 nums1 中查找第 k/2 小的数 int mid2 = k - mid1; // 在 nums2 中查找第 k-mid1 小的数 if (nums1[mid1 - 1] < nums2[mid2 - 1]) { // nums1 的前 mid1 个数都不是第 k 小的数 return findKthSmallest(nums1 + mid1, nums1Size - mid1, nums2, nums2Size, k - mid1); } else if (nums1[mid1 - 1] > nums2[mid2 - 1]) { // nums2 的前 mid2 个数都不是第 k 小的数 return findKthSmallest(nums1, nums1Size, nums2 + mid2, nums2Size - mid2, k - mid2); } else { // 找到了第 k 小的数 return nums1[mid1 - 1]; } } 时间复杂度分析：每次查找时，我们都可以排除掉 k/2 个数，因此最多需要查找 log(k) 次，即时间复杂度为 O(log(k))。由于 k 最大为 m+n，因此时间复杂度为 O(log(m+n))。