class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if(nums1.length>nums2.length){
return findMedianSortedArrays(nums2,nums1);
}
int nums1Size = nums1.length,nums2Size = nums2.length;
int x = nums1Size >> 1;
int y = (nums1Size + nums2Size + 1) >> 1;
int low = 0;
int high = nums1Size;
while(low <= high){
int xcut = (low + high) >> 1;
int ycut = y - xcut;
int xleft = xcut == 0?Integer.MIN_VALUE:nums1[xcut-1];
int xright = xcut == nums1Size?Integer.MAX_VALUE:nums1[xcut];
int yleft = ycut == 0?Integer.MIN_VALUE:nums2[ycut-1];
int yright = ycut == nums2Size?Integer.MAX_VALUE:nums2[ycut];
if(xleft<=yright && xright>=yleft){
if((nums1Size + nums2Size)%2 == 0){
return ((double)(Math.max(xleft,yleft) + Math.min(xright,yright)))/2;
}else{
return (double) Math.max(xleft,yleft);
}
}else if(xleft > yright){
high = xcut -1;
}else {
low = xcut + 1;
}
}
return 0.0;
}
}
此算法的关键是：在两个数组里面找最中间的数（4个）；
在求中位数的时候必然有一个整合数组，输出的double中位数应该是这个整合数组的中位数，而这个算法是找出中间的4个数，然后就能得出中位数。
因为xleft和xrigh总是在一起的数，而 yleft yright也总是nums2连续的数
有xleft <= xright yleft <= yright
如果满足：xleft<=yright && xright>=yleft
就说明nums1上的两个数在nums2两个数之间 所以这4个数一定是整合数组里面的连续的值
nums1.length < nums2.length
每次都是从数组中间去取。逐渐往整合数组中间靠拢。
如果数组达到了边界，左边的按照minvalue 填充 因为 left都是求最大值 右边求最小值。
