Binary search --- Java, made some improvement on corner case check


  • 0
    M
    public class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            if(nums1.length > nums2.length){
                return findMedianSortedArrays(nums2, nums1);
            }
            boolean isEven = (nums1.length + nums2.length) % 2 == 0;
            if(nums1.length == 0){
                return isEven ? (nums2[nums2.length / 2 - 1]  + nums2[nums2.length / 2]) / 2.0 : nums2[nums2.length / 2];
            }
            int start = 0, end = nums1.length;
            
            int i = 0;
            int maxLeft = 0;
            int minRight = 0;
            while(start <= end){
                i = start + (end - start) / 2;
                int j = (nums1.length + nums2.length + 1) / 2 - i;
    
                if(i < nums1.length && nums1[i] < nums2[j - 1]){
                    // move i to right side
                    start = i + 1;
                }else if(i > 0 && nums1[i-1] > nums2[j]){
                    // move i to left side
                    end = i - 1;
                }else{
                    if(i == 0){
                        maxLeft = nums2[j - 1];
                    }else if(j == 0){
                        maxLeft = nums1[i - 1];
                    }else{
                        maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                    }
                    
                    if(i == nums1.length){
                        minRight = nums2[j];
                    }else if(j == nums2.length){
                        minRight = nums1[i];
                    }else{
                        minRight = Math.min(nums1[i], nums2[j]);
                    }
                    
                    return isEven ? (minRight + maxLeft) / 2.0 : maxLeft; 
                }
            }
            return 0.0;
            
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.