[LeetCode][0004] median of Two Sorted Arrays

 

 

 

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int nums1_size = nums1.size();
        int nums2_size = nums2.size();
        
        if(nums1_size > nums2_size) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int left = 0, right = nums1_size;
        int mid = (nums1_size + nums2_size + 1) / 2;
        
        int max_of_left = -1, min_of_right = -1;
        while(left <= right) {
            int i = (left + right) / 2;
            int j = (mid - i);
            
            if(i < nums1_size && nums1[i] < nums2[j - 1]) {
                left = i + 1;
            } else if(i > 0 && nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                if(i == 0) {
                    max_of_left = nums2[j - 1];
                } else if(j == 0) {
                    max_of_left = nums1[i - 1];
                } else {
                    max_of_left = max(nums1[i - 1], nums2[j - 1]);
                }
                
                if((nums1_size + nums2_size) % 2 == 1) {
                    return max_of_left;
                }
                
                if(i == nums1_size) {
                    min_of_right = nums2[j];
                } else if(j == nums2_size) {
                    min_of_right = nums1[i];
                } else {
                    min_of_right = min(nums1[i], nums2[j]);
                }
                return (max_of_left + min_of_right) / 2.0;
            }
        }
        return -1.0;
    }
};