#include <stdio.h>
#include <limits.h>

// 比较两个整数的最大值
int max(int a, int b) {
    return a > b ? a : b;
}

// 比较两个整数的最小值
int min(int a, int b) {
    return a < b ? a : b;
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    // 确保对较短的数组进行二分查找，优化时间复杂度
    if (nums1Size > nums2Size) {
        return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
    }
    
    int m = nums1Size;
    int n = nums2Size;
    int left = 0;          // 二分查找的左边界
    int right = m;         // 二分查找的右边界（取m而非m-1，确保能取到所有可能的分割点）
    
    while (left <= right) {
        // 计算nums1的分割点
        int midA = (left + right) / 2;
        // 计算nums2的分割点，确保总数组左右两部分总长度相等（或左比右多1）
        int midB = (m + n + 1) / 2 - midA;
        
        // 处理分割点在数组边界的情况（极端情况）
        int leftA = (midA == 0) ? INT_MIN : nums1[midA - 1];
        //midA在左边界 其中INT_MIN、INT_MAX 看做正负最大值
        int rightA = (midA == m) ? INT_MAX : nums1[midA];
        int leftB = (midB == 0) ? INT_MIN : nums2[midB - 1];
        int rightB = (midB == n) ? INT_MAX : nums2[midB];
        
        // 检查当前分割是否满足条件：左半部分所有元素 <= 右半部分所有元素
        if (leftA <= rightB && leftB <= rightA) {
            // 总长度为奇数时，中位数是左半部分的最大值
            if ((m + n) % 2 == 1) {
                return (double)max(leftA, leftB);
            } else {
                // 总长度为偶数时，中位数是左半部分最大值与右半部分最小值的平均值
                return (double)(max(leftA, leftB) + min(rightA, rightB)) / 2.0;
            }
        } else if (leftA > rightB) {
            // 左A太大，需要左移分割点
            right = midA - 1;
        } else {
            // 左B太大，需要右移分割点
            left = midA + 1;
        }
    }
    
    // 理论上不会走到这里，因为题目保证数组非空且有解
    return 0.0;
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int total = nums1Size + nums2Size;
    if (total == 0) return 0.0; // 处理空数组
    
    int k = total / 2; // 偶数时需第k和k-1个元素，奇数时需第k个元素
    int i = 0, j = 0;
    int first = 0, second = 0; // 存储中间的两个元素
    
    // 遍历获取前k+1个元素，最终first=第k-1个，second=第k个
    for (int count = 0; count <= k; count++) {
        first = second; // 每次迭代将前一个值赋给first
        
        // 严格检查边界，避免越界
        if (i >= nums1Size) {
            // nums1已遍历完，取nums2的元素
            second = nums2[j++];
        } else if (j >= nums2Size) {
            // nums2已遍历完，取nums1的元素
            second = nums1[i++];
        } else if (nums1[i] < nums2[j]) {
            // 取较小的元素
            second = nums1[i++];
        } else {
            second = nums2[j++];
        }
    }
    
    // 根据总长度奇偶性计算中位数
    if (total % 2 == 1) {
        // 奇数：直接返回第k个元素（second）
        return (double)second;
    } else {
        // 偶数：返回第k-1个（first）和第k个（second）的平均值
        return (double)(first + second) / 2.0;
    }
}