[LeetCode] 4. Median of Two Sorted Arrays

Link here

An excellent binary search problem. It’s easy to use brute-force or mergesort to solve it, but the time complexity is specified as $O(log(m+n))$ in the problem.

It’s obvious to think of binary search when noticing the time complexity with “log”, but constructing such a algorithm remains to be a big problem.

Here are three ways to solve the problem:

Method1: O(log(m)*log(n))

As we are going to find the median of the two sorted arrays, which means we are going to find the k-th(or (k+1)-th) of the two arrays, we can use binary search to find the rank of each number in the array.

For example, as we have picked up one single number from array A, we can use binary search to determine how many numbers in array B are smaller than this single number. Then, we can calculate the rank of this number simply, and the time complexity of it is $O(log(n))$ or $O(log(m))$.

But now we are going to find the median, so another binary search is needed. For the first array A, we apply binary search to it. And for each turn, we can calculate the rank of the select number, and move the boundary to left or right after comparing the rank with median rank(i,e., $(n+m+1)/2$).

In this way, we can solve the problem in $O(log(m)*log(n))$.

Method2: O(log(m*n))

The key operations are specified in the following picture:

For every turn of binary search, at least half of one array can be abandoned, thus decreasing the size of the searching space.

Method3: O(log(min(m, n)))

We can only consider about applying binary search in one single array, and now we apply it to the shorter array.

After we determine the partition point of array A($partitionA$), we can calculate the partition point in array B($(n+m+1)/2-paritionA$), show shown in the picture below.

Now we can compare the edge elements.

Here maxLeftA is partitionA, and maxLeftB is partitionB. By comparing these four elements, we can have the following conclusions:

• maxLeftA<=minRightA, maxLeftB<=minRightB, because the array is sorted.
• if maxLeftA<=minRightB, and maxLeftB<=minRightA, then we find the answer.
• if maxLeftA<=minRightB, and maxLeftB>minRightA, we move the binary boundary to right.
• if maxLeftA>minRightB, and maxLeftB<=minRightA, we move the binary boundary to left.
• it’s impossible that maxLeftA>minRightB, and maxLeftB>minRightA.

So we can solve the problem in $O(log(min(m, n)))$.

The code is shown below.

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size(); 
        if (m > n) return findMedianSortedArrays(nums2, nums1); 
        int l1, l2, r1, r2; 
        int l = 0, r = m, mid1, mid2; 
        while (l <= r) { 
            mid1 = (l + r) >> 1;
            mid2 = (m + n + 1) / 2 - mid1; 

            int l1 = (mid1 == 0) ? INT_MIN : nums1[mid1 - 1]; 
            int r1 = (mid1 == m) ? INT_MAX : nums1[mid1]; 
            int l2 = (mid2 == 0) ? INT_MIN : nums2[mid2 - 1]; 
            int r2 = (mid2 == n) ? INT_MAX : nums2[mid2]; 

            if (l1 <= r2 && l2 <= r1) {
                if ((n + m) % 2 == 1) return max(l1, l2); 
                else 
                    return ((double)max(l1, l2) + min(r1, r2)) / 2;
            }
            else if (l1 <= r2 && l2 > r1) {
                l = mid1 + 1; 
            }
            else if (l1 > r2 && l2 <= r1) { 
                r = mid1 - 1; 
            }
        }
        return 0.0; 
    }
};