MockInterview:4. Median of Two Sorted Arrays

Hard

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Solution:
the median means divide the set into two equal length set, or one set always has one more element than the other set.
Let's cut A into two set at random i

      left_A             |        right_A
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]

0   1          i-1      i        i+1         m-1        m

Since A has m elements, so there are m+1 ways of cutting. when index = 0, length(left_A) = 0, when index = m, length(left_A) = m

With the same way, cut B into two parts at a random position j:

      left_B             |        right_B
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

put left_A and left_B into one set, and put right_A and right_B into one set. Let's name them left_part and right_part :

      left_part          |        right_part
A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

If we can ensure:
1) length(left_part) = length(right_part)
2) A[i-1] < B[j] and B[j-1] < A[i]

to make sure left part is always larger or equal than right part. the length of left part is (m+n+1)/2.
take 8 for example, left part is 4, right part is 4.
take 9 for example, left part is 5, right part is 4.

1) take middle number of left_A element quantity = (0+m)/2 as index, to keep left part and right part the same or one element greater, left_B should be length(left part) - length(left_A) = (m+n+1)/2 - (0+m)/2;
2) make sure all left part is smaller than right part. so make sure  A[i-1] < B[j] and B[j-1] < A[i].
if A[i-1] > B[j], it means search the smaller element in array A, search on left side of the array A.
B[j-1] > A[i], it means search the greater element is array A, search on right side of the array A.
3) if the length of left_A is 0, it means the max of left part is Integer.MIN_VALUE, any element is greater than it.(the condition always is  satisfied)
    if the length of left_A is m, it means the min of right part is Integer.MAX_VALUE, any element is smaller than it.(the condition always is  satisfied).
4) the number of the length is odd, the median is the max of the left part, Math.max(left[i-1],B[j-1]).
    if the number of the length is even, the median is (max(left part) + min(right_part) )/ 2

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length > nums2.length){
            return findMedianSortedArrays(nums2,nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
        int min = 0;//not the min index, the min quantity in the left;
        int max = m;//not the max index, the max quantity in the left;because there are m element, there are m+1 ways of cutting.
        int totalLeft = (n + m + 1)/2;//always make sure left part has the same elements or one more element than right part. so need to add 1. when there is 9 element, make sure left part has 5 elements total. so add 1.
        double mid = 0;
        while(min <= max){
            int partition1 = (min + max)/2;
            int partition2 = totalLeft - partition1;
            int left1 = partition1 == 0 ? Integer.MIN_VALUE:nums1[partition1-1];
            int right1 = partition1 == m ? Integer.MAX_VALUE: nums1[partition1];
            
            System.out.println(partition2);
            int left2 = partition2 == 0 ? Integer.MIN_VALUE:nums2[partition2-1];
            int right2 = partition2 == n ? Integer.MAX_VALUE: nums2[partition2];
            
            if(left1 <= right2 && left2 <= right1){
                if((n + m) % 2 == 0){
                    mid = ((double)Math.max(left1, left2) + Math.min(right1, right2))/2;
                }else{
                    mid = Math.max(left1, left2);
                }
                break;
            }else if(left1 > right2){
                max = partition1 - 1;
            }else{
                min = partition1 + 1;
            }
        }
        return mid;
    }
}