Given two sorted arrays, a[] and b[], the task is to find the median of these sorted arrays, in O(log n + log m) time complexity, when n is the number of elements in the first array, and m is the number of elements in the second array.

How to Solve

  1. Let assume that there are two arrays A and B with array A having the minimum number of elements. If this is not the case than swap A and B to make A having small size.
  2. The edge cases like one array is empty or both are empty will be handled.
    1. let n be the size of A and m be the size of B.
    2. Now think of an idea that if we have to find the median than we have to divide the whole merged array into two parts namely left and right parts.
    3. Now since we are given the size of left part (i.e (n+m+1)/2), Now look at below given example. 
      A-> 1,2,3,4,5     n = 5
B-> 1,2,3,4,5,6   m = 6

      Here merged array will look like :- 1,1,2,2,3,3,4,4,5,5,6 and median then is 3

    4. Now we can see our left part which is in orange.
    5. We divide A and B into two parts such that the sum of left part of both A and B will result in left part of merged array. 
      A-> 1,2,3,4,5     // pointers l =0 and r = n-1 hence mid = (l+r)/2;
B -> 1,2,3,4,5,6

      we can see that left part of A is given as n/2 and since total length of left part in merged array is (m+n+1)/2, so left part of B = (m+n+1)/2-n/2;

      Now we just have to confirm if our left and right partitions in A and B are correct or not.

  3. Now we have 4 variables indicating four values two from array A and two from array B. 
    leftA -> Rightmost element in left part of A = 2
leftb -> Rightmost element in left part of B = 4
rightA -> Leftmost element in right part of A = 3
rightB -> Leftmost element in right part of B = 5

    Hence to confirm that partition is correct we have to check the following conditions.

    leftA<=rightB and leftB<=rightA // This is the case when the sum of two parts of A and B results in left part of merged array

    if our partition not works that means we have to find other mid point in A and then left part in B This is seen when

    leftA > rightB    //means we have to dec size of A's partition
so do r = mid-1;
else
do l =mid+1;

    Hence repeat the above steps with new partitions till we get the answers.

  4. If leftA<=rightB and leftB<=rightA then we get correct partition and our answer depends on the total size of merged array (i.e. m+n) 
    If (m+n)%2==0
ans is max(leftA,leftB)+min(rightA,rightB)/2; // max of left part is nearest to median and min of right part is nearest to medain
else
ans is max(leftA,leftB);

Test Cases

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Solution

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        if (n1 > n2) return findMedianSortedArrays(nums2, nums1);
        int start = 0, end = n1;
        while(start <= end) {
            int mid1 = start + (end-start)/2;
            int mid2 = (n1+n2+1)/2 - mid1;
            int x1 = mid1 == 0 ? INT_MIN : nums1[mid1-1];
            int x2 = mid2 == 0 ? INT_MIN : nums2[mid2-1];
            int y1 = mid1 == n1 ? INT_MAX : nums1[mid1];
            int y2 = mid2 == n2 ? INT_MAX : nums2[mid2];
            if (x1 <= y2 && x2 <= y1) {
                if ((n1+n2)%2 == 0) {
                    return (max(x1, x2) + min(y1, y2)) /2.0;
                } else {
                    return max(x1, x2);
                }
            }
            if (x1 > y2) {
                end = mid1 - 1;
            } else {
                start = mid1 + 1;
            }
        }
        return -1;
    }
};
import java.lang.*;

class Solution {
    private static double findMedian(int[] arr1, int[] arr2) {
        int n1 = arr1.length, n2 = arr2.length;
        if (n1 > n2) return findMedian(arr2, arr1);
        int start = 0, end = n1;
        while(start <= end) {
            int mid1 = start + (end - start)/2;
            int mid2 = (n1+n2+1)/2 - mid1;
            int x1 = mid1 == 0 ? Integer.MIN_VALUE : arr1[mid1 - 1];
            int x2 = mid2 == 0 ? Integer.MIN_VALUE : arr2[mid2 - 1];
            int y1 = mid1 == n1 ? Integer.MAX_VALUE : arr1[mid1];
            int y2 = mid2 == n2 ? Integer.MAX_VALUE : arr2[mid2];
            if (x1 <= y2 && x2 <= y1) {
                if ((n1+n2)%2 == 0) {
                    return (Math.max(x1, x2) + Math.min(y1, y2)) / 2.0;
                }
                return Math.max(x1, x2);
            }
            if (x1 > y2) {
                end = mid1 - 1;
            } else {
                start = mid1 + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr1 = { -5, 3, 6, 12, 15 };
        int[] arr2 = { -12, -10, -6, -3, 4, 10 };
        System.out.println(findMedian(arr1, arr2));
    }
}
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        n1, n2 = len(nums1), len(nums2)
        if n1 > n2:
            return self.findMedianSortedArrays(nums2, nums1)
        start, end = 0, n1
        while start <= end:
            m1 = start + (end-start)//2
            m2 = (n1+n2+1)//2 - m1
            x1 = float('-inf') if m1 == 0 else nums1[m1-1]
            x2 = float('-inf') if m2 == 0 else nums2[m2-1]
            y1 = float('inf') if m1 == n1 else nums1[m1]
            y2 = float('inf') if m2 == n2 else nums2[m2]
            if x1 <= y2 and x2 <= y1:
                if (n1+n2)%2 == 0:
                    return (max(x1, x2) + min(y1, y2))/2
                return max(x1, x2)
            elif x1 > y2:
                end = m1 - 1
            else:
                start = m1 + 1
        return -1
Time Complexity: O(log(m+n))
Space Complexity: O(1)