Median of Two Sorted Array.cpp

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = (int) nums1.size();
        int m = (int) nums2.size();

        int low = 0, high = n;
        int posINF = INT_MAX, negINF = INT_MIN;
        int median = (n+m)/2 + 1;
        bool odd = ((n+m)%2 == 1);
        double ans;
        while(low <= high){
            int cnt1 = (low+high)/2;
            int cnt2 = median-cnt1;
            if(cnt2 < 0) high = cnt1-1;
            else if(cnt2 > m) low = cnt1+1;
            else {
                int curNum1 = negINF, curNum2 = negINF;
                if(cnt1 > 0) curNum1 = nums1[cnt1-1];
                if(cnt2 > 0) curNum2 = nums2[cnt2-1];
                int curMaximum = max(curNum1, curNum2);

                int nextNum1 = posINF, nextNum2 = posINF;
                if(cnt1 < n) nextNum1 = nums1[cnt1];
                if(cnt2 < m) nextNum2 = nums2[cnt2];
                int nextMinimum = min(nextNum1, nextNum2);
                if(curMaximum <= nextMinimum){
                    if(odd) ans = (double) max(curNum1, curNum2);
                    else {
                        int prevNum1 = negINF, prevNum2 = negINF;
                        if(cnt1 > 1) prevNum1 = nums1[cnt1-2];
                        if(cnt2 > 1) prevNum2 = nums2[cnt2-2];
                        int maxs = max(curNum1, curNum2);
                        if(curNum1 == maxs){
                            maxs += max(prevNum1, curNum2);
                        }
                        else {
                            maxs += max(prevNum2, curNum1);
                        }
                        ans = (double) maxs/2.0;
                    }
                    break;
                }
                else {
                    if(curNum1 > nextMinimum) high = cnt1-1;
                    else low = cnt1+1;
                }
            }
        }
        return ans;
    }
};