Description

tags: Array, Binary Search, Divide and Conquer

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

关键点

将题目的变量控制为只有i，转化为二分查找合适的i值。i在imin和imax之间。
i确定时j也是确定的，因为有限制条件：i + j == (m - i) + (n - j)。
那么问题就简单了，二分查找在imin和imax之间的i。对于某一个特定的i，有三种情况（在不考虑edge case时），分别是：

1. A[i-1] <= B[j]，B[j] <= A[i]刚好满足条件，找到我们要的i
2. A[i-1] > B[j]，i需要左移。令imax = i - 1
3. B[j -1] > A[i]，i需要右移。令imin = i+1

My solution

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        // ensure nums1(m elems) is the shorter one. m <= n
        if (nums1.size() > nums2.size()) {
            nums1.swap(nums2);
        }
        int m = nums1.size();
        int n = nums2.size();
        
        int low = 0, high = m;
        double median = 0;
        bool isEven = ((m + n) % 2 == 0 ? true : false);
        while (low <= high) {
            int i = (low + high) / 2;
            int j = (m + n) / 2 - i;
            if (j < n && i > 0 && nums1[i-1] > nums2[j]) {
                high = i - 1; // i is too small
            } 
            else if (i < m && j > 0 && nums1[i] < nums2[j-1]) {
                low = i + 1; // i is too big
            } 
            else {
                double rightMin = 0, leftMax = 0;
                
                if (i == 0) leftMax = nums2[j-1];
                else if (j == 0) leftMax = nums1[i-1];
                else leftMax = max(nums1[i-1], nums2[j-1]);
                
                if (i == m) rightMin = nums2[j];
                else if (j == n) rightMin = nums1[i];
                else rightMin = min(nums1[i], nums2[j]);
                
                median = isEven ? (leftMax + rightMin) / 2 : rightMin;
                return median;
            }
        }
        
        return 0.0;        
    }
};

Point

这题太难了。。。要反复做。。好好理解条件判断。。。TAT