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:

Doing binary search to input which has smaller length

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int x = nums1.length;
        int y = nums2.length;
        
        //make sure length of first input is always smaller than second input
        //always do the binary search to the input which has smaller length
        if (x > y) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int left = 0;
        int right = x;
        while (left <= right) {
            int partitionX = (right + left) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;
            
            //if partitionX is 0 it means nothing is there on left side. Use -INF for maxLeftX
            //if partitionX is length of input then there is nothing on right side. Use +INF for minRightX
            int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
            
            int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
            
            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                //x + y is odd:     median = (maxL + minR) / 2
                //x + y is even:    median = maxL
                if ((x + y) % 2 == 0) {
                    return ((double) Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
                } else {
                    return (double) Math.max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) { //too far on right side for partitionX. Go on left side
                right = partitionX - 1;
            } else { //too far on left side for partitionX. Go on right side
                left = partitionX + 1;
            }
        }
        //if input arrays were not sorted. Throw in that scenario.
        throw new IllegalArgumentException();
    }
}

Time complexity: O(log(min(m, n)))

Space complexity: O(1), store local variables