public double findMedianSortedArrays(int[] nums1,int[] nums2){
  int m=nums1.length;
  int n=nums2.length;
  if (m > n) {
    return findMedianSortedArrays(nums2,nums1);
  }
  int i=0;
  int j=0;
  int iMin=0;
  int iMax=m;
  int mid=(m + n + 1) / 2;
  while (iMin <= iMax) {
    i=(iMin + iMax) / 2;
    j=mid - i;
    if (j > 0 && i < m && nums2[j - 1] > nums1[i]) {
      iMin=i + 1;
    }
 else     if (i > 0 && j < n && nums1[i - 1] > nums2[j]) {
      iMax=i - 1;
    }
 else {
      break;
    }
  }
  int leftMax=0;
  if (i == 0) {
    leftMax=nums2[j - 1];
  }
 else   if (j == 0) {
    leftMax=nums1[i - 1];
  }
 else {
    leftMax=Math.max(nums1[i - 1],nums2[j - 1]);
  }
  if ((m + n) % 2 == 1) {
    return leftMax;
  }
  int rightMin=0;
  if (i == m) {
    rightMin=nums2[j];
  }
 else   if (j == n) {
    rightMin=nums1[i];
  }
 else {
    rightMin=Math.min(nums1[i],nums2[j]);
  }
  return (leftMax + rightMin) / 2.0;
}

public double findMedianSortedArrays ( int [ ] nums1 , int [ ] nums2 ) { int m = nums1 . length ; int n = nums2 . length ; if ( m > n ) { return findMedianSortedArrays ( nums2 , nums1 ) ; } int i = 0 ; int j = 0 ; int iMin = 0 ; int iMax = m ; int mid = ( m + n + 1 ) / 2 ; while ( iMin <= iMax ) { i = ( iMin + iMax ) / 2 ; j = mid - i ; if ( j > 0 && i < m && nums2 [ j - 1 ] > nums1 [ i ] ) { iMin = i + 1 ; } else if ( i > 0 && j < n && nums1 [ i - 1 ] > nums2 [ j ] ) { iMax = i - 1 ; } else { break ; } } int leftMax = 0 ; if ( i == 0 ) { leftMax = nums2 [ j - 1 ] ; } else if ( j == 0 ) { leftMax = nums1 [ i - 1 ] ; } else { leftMax = Math . max ( nums1 [ i - 1 ] , nums2 [ j - 1 ] ) ; } if ( ( m + n ) % 2 == 1 ) { return leftMax ; } int rightMin = 0 ; if ( i == m ) { rightMin = nums2 [ j ] ; } else if ( j == n ) { rightMin = nums1 [ i ] ; } else { rightMin = Math . min ( nums1 [ i ] , nums2 [ j ] ) ; } return ( leftMax + rightMin ) / 2.0 ; }
binary search . first figure out what we are to search for . there are one cut point for each array , i for nums1 , j for nums2 . then we have four smaller arrays : nums1 [ 0 ~ i - 1 ] , nums2 [ 0 ~ j - 1 ] , nums1 [ i , m - 1 ] , nums2 [ j , n - 1 ] if we name them a , b , c , d , respectively , then the desired values for i and j should make : 1 ) len ( a ) + len ( b ) = len ( c ) + len ( d ) = > i + j = m + n - i - j or m + n + 1 - i - j 2 ) nums1 [ i - 1 ] < = nums2 [ j ] & & nums2 [ j - 1 ] < = nums1 [ i ] < p > if the # of elements is odd , the median is max ( a , b ) if even , the median is ( max ( a , b ) + min ( c , d ) ) / 2 < p > https : / / discuss . leetcode . com / topic / 4996 / share - my - o - log - min - m - n - solution - with - explanation / 2
