1 3 5 7 8
2 4 6 9
#1#3#5#7#8# 10/2 = 5
#2#4#6#9# 8/2 = 4
#1#3#5 (C1) 5#7#8#
L1: 1 3 5
R1: 5 7 8
#2#4 #(C2) 6#9#
L2: 2 4
R2: 6 9
找到中位数就是找到L1最大的数小于R2最小的数，同时L2最大的数小于R1最小的数
然后在找到的L1,L2中两个数取最大值，R1/R2中的两个数取最小值即可
查找目标：
maxL1 < minR2 && maxL2 < minR1
查找过程：
如果maxL1 > minR2 ,说明R2中开头包含太多的数导致minR2 < maxL1 ,需要把C2向右移动，让R2最小值变大 就是lo = mid2+1
同理如果maxL2 > minR1,说明L2中包含太多的数导致maxL2 > minR1, 需要左移动C2让L2的最大值变小，知道maxL2 < minR1, 也就是hi = mid2-1;
*L1 就是L1的最大值，R1就是R1的最小值
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
int N1 = nums1Size;
int N2 = nums2Size;
if (N1 < N2) return findMedianSortedArrays(nums2, nums2Size, nums1,nums1Size); // Make sure A2 is the shorter one.
int lo = 0, hi = N2 * 2;
while (lo <= hi) {
int mid2 = (lo + hi) / 2; // Try Cut 2
int mid1 = N1 + N2 - mid2; // Calculate Cut 1 accordingly
double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2]; // Get L1, R1, L2, R2 respectively
double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1)/2];
double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2)/2];
if (L1 > R2) lo = mid2 + 1; // A1's lower half is too big; need to move C1 left (C2 right)
else if (L2 > R1) hi = mid2 - 1; // A2's lower half too big; need to move C2 left.
else return (max(L1,L2) + min(R1, R2)) / 2; // Otherwise, that's the right cut.
}
return -1;
}
