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

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

中位数定义：
合并后数组长度为奇数：中位数 = 中间那个数；
合并后数组长度为偶数：中位数 = 中间两个数的平均值。

思路：再解释之前先给大家看一段话，从 nums1 最左边开始，一点点把 nums1 的数划到左半部分，直到 nums1 右半的第一个数比 nums2 左半的最后一个数大，此时分割点就对了。这就是这道题核心，大家参考这段话再看后续。
把两个原数组分别分割成「左半部分」和「右半部分」，通过分割点满足的条件，直接推导中位数，无需合并。
分割需满足的两个关键条件：
1、长度平衡：nums1左 + nums2左的总长度 = nums1右 + nums2右的总长度（或多 1 个，适配奇数长度）；
2、数值有序：左半部分所有数 ≤ 右半部分所有数（即 nums1左最大值 ≤ nums2右最小值且 nums2左最大值 ≤ nums1右最小值）。
满足这两个条件后：
奇数长度：中位数 = 左半部分的最大值（左半多的那个数就是中间数）；
偶数长度：中位数 = (左半最大值 + 右半最小值) / 2。

推导：
首先需要保证 nums1（代码里用 m 表示长度）是较短的数组，只需要在短数组上枚举分割点，减少循环次数，把时间复杂度降到 O(min(m,n))（比合并数组的 O (m+n) 高效）。其次避免特殊情况（比如 nums1 全在左半，分割点在最右端，此时 nums1右无元素，用 INT_MAX 代替；分割点在最左端，nums1左无元素，用 INT_MIN 代替）；
初始化分割点 —— 保证长度平衡：j = (m+n+1)/2 - i（初始 i=0，所以 j=(m+n+1)/2）：保证 i + j = (m+n+1)/2，即左半部分总长度是「合并后数组长度的一半（或多 1）」，满足「长度平衡」条件。如果 nums1右第一个数 ≤ nums2左最后一个数，说明 nums1 的分割点可以右移（i++），让 nums1 多拿一个数到左半（同时 j--，保证 i+j 总长度不变）；
循环终止条件：nums1右第一个数 > nums2左最后一个数，此时分割点满足「数值有序」（左半所有数 ≤ 右半所有数）。
max1：左半部分的最大值（nums1左最后一个数和 nums2左最后一个数中的较大值）；
min2：右半部分的最小值（nums1右第一个数和 nums2右第一个数中的较小值）；
最终返回：
奇数长度（(m+n)%2 == 1）：直接返回左半最大值 max1；
偶数长度：返回 (max1 + min2)/2.0（除以 2.0 保证是浮点数）。

#define MAX(a,b) ((b) > (a) ? (b) : (a))
#define MIN(a,b) ((b) < (a) ? (b) : (a))

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int m = nums1Size;
    int n = nums2Size;
   // 保证nums1是较短的数组，减少后续枚举分割点的次数
    if(m > n) {
        return findMedianSortedArrays(nums2, n, nums1, m);
    }
    int* a = malloc((m + 2) * sizeof(int));
    int* b = malloc((n + 2) * sizeof(int));
    a[0] = b[0] = INT_MIN;        // 左哨兵：负无穷，处理分割点在数组最左端的情况（左半无元素）
    a[m + 1] = b[n + 1] = INT_MAX;     // 右哨兵：正无穷，处理分割点在数组最右端的情况（右半无元素）
    memcpy(a + 1, nums1, m * sizeof(int));    // 把原nums1复制到扩容数组a的[1, m]位置（中间区域）
    memcpy(b + 1, nums2, n * sizeof(int));     // 把原nums2复制到扩容数组b的[1, n]位置
    // 初始化分割点：满足左半部分总长度平衡
    // i：nums1左半部分的元素个数（初始为0，即nums1左半为空）
    // j：nums2左半部分的元素个数
    // (m+n+1)/2：左半部分总长度（保证奇数长度时左半多1个，直接取左半最大值为中位数）
    int i = 0, j = (m + n + 1 )/2;
    // a[i+1]：nums1右半部分的第一个数
    // b[j]：nums2左半部分的最后一个数
    while (a[i + 1] <= b[j]){
        i++;       // nums1左半个数+1（分割点右移）
        j--;        // nums2左半个数-1（保证左半总长度不变）
    }
   // max1：左半部分的最大值（nums1左最后一个数 和 nums2左最后一个数 的较大值）
    int max1 = MAX(a[i], b[j]);          
     // min2：右半部分的最小值（nums1右第一个数 和 nums2右第一个数 的较小值）
    int min2 = MIN(a[i+1], b[j+1]);
    free(a);
    free(b);
    return (m + n)% 2 ? max1 : (max1 + min2) / 2.0; 
}