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;
}
}
此算法的關(guān)鍵是：在兩個(gè)數(shù)組里面找最中間的數(shù)（4個(gè)）；
在求中位數(shù)的時(shí)候必然有一個(gè)整合數(shù)組，輸出的double中位數(shù)應(yīng)該是這個(gè)整合數(shù)組的中位數(shù)，而這個(gè)算法是找出中間的4個(gè)數(shù)，然后就能得出中位數(shù)瘫筐。
因?yàn)閤left和xrigh總是在一起的數(shù)，而 yleft yright也總是nums2連續(xù)的數(shù)
有xleft <= xright yleft <= yright
如果滿足：xleft<=yright && xright>=yleft
就說明nums1上的兩個(gè)數(shù)在nums2兩個(gè)數(shù)之間 所以這4個(gè)數(shù)一定是整合數(shù)組里面的連續(xù)的值
nums1.length < nums2.length
每次都是從數(shù)組中間去取铐姚。逐漸往整合數(shù)組中間靠攏策肝。
如果數(shù)組達(dá)到了邊界，左邊的按照minvalue 填充 因?yàn)? left都是求最大值 右邊求最小值隐绵。
