4. Median of Two Sorted Arrays

There are two sorted arrays nums1and 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)).

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

Thoughts:

use binary search to find the best partition i and j in nums1 and nums2 such that nums1[i] > nums 2[j -1] && nums2[j] > nums1[i -1]. Also j = (m + n +1 )/ 2 - j (for n as the "longer" array length and m as the "shorter" array length, m >= n) to guarantee that i + j is the median position for odd number total length and left input of computing median for even total length.

Code Time Complexity: O(min(m,n)), Space Complexity: O(1)

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 i, j, imin = 0, imax = m, half = (m + n + 1) / 2;
        // bianry search to get optimal i
            while (imin <= imax) {
            i = (imin & imax) + ((imin ^ imax) >> 1); //(imin + imax)/2
            j = half - i;
            if (i > 0 &&  nums1[i - 1] > nums2[j]) imax = i - 1; // i too big, must decrease it.
            else if (i < m && nums2[j - 1] > nums1[i]) imin = i + 1; // it too small, must increase it.
            else break;
        }
        int max_left;
        if(!i) max_left = nums2[j - 1]; 
        else if(!j) max_left = nums1[i - 1];
        else max_left = max(nums1[i - 1], nums2[j - 1]);

        if ((m + n) & 1) return max_left; // if m + n is odd
        int min_right;

        if(i == m) min_right = nums2[j];
        else if(j == n) min_right = nums1[i];
        else min_right = min(nums1[i],nums2[j]);

        return (max_left + min_right)/ 2.0;

    }
};

Special Thanks to missmary's solution& explanation and jianchao.li.fighter's code