Median_of_Two_Sorted_Arrays_Divide.cpp

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 iMin = 0, iMax = N1;
        while(iMin <= iMax)
        {
            int i = (iMin + iMax) / 2;
            int j = (N1 + N2 +1)/2 - i;
            
            if(i!=N1 && j!=0 && nums2[j-1] > nums1[i])
                iMin = i + 1;
            else if(j!=N2 && i!=0 && nums1[i-1] > nums2[j])
                iMax = i - 1;
            else
            {
                int maxLeft = 0;
                if(i == 0) {
                     maxLeft = nums2[j - 1];
                }
                else if(j == 0)
                {
                    maxLeft = nums1[i - 1];
                }  
                else{
                    maxLeft = max(nums1[i-1], nums2[j-1]);
                }
                    
                if((N1 + N2) %2 == 1) return maxLeft;
                
                int minRight = 0;
                if(i == N1){
                    minRight = nums2[j];
                } 
                else if(j == N2){
                    minRight = nums1[i];
                }
                else{
                    minRight = min(nums1[i], nums2[j]);
                }
                    
                return (maxLeft + minRight)/2.0;
                
            } 
        }
        return 0;        
    }
};