findMedianSortedArrays.java

class MedianFinder {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        // Ensure nums1 smaller array ho
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int x = nums1.length;
        int y = nums2.length;

        int low = 0;
        int high = x;

        while (low <= high) {

            int partitionX = (low + high) / 2;
            int partitionY = (x + y + 1) / 2 - partitionX;

            int maxLeftX =
                    (partitionX == 0)
                    ? Integer.MIN_VALUE
                    : nums1[partitionX - 1];

            int minRightX =
                    (partitionX == x)
                    ? Integer.MAX_VALUE
                    : nums1[partitionX];

            int maxLeftY =
                    (partitionY == 0)
                    ? Integer.MIN_VALUE
                    : nums2[partitionY - 1];

            int minRightY =
                    (partitionY == y)
                    ? Integer.MAX_VALUE
                    : nums2[partitionY];

            // Correct partition mil gaya
            if (maxLeftX <= minRightY &&
                maxLeftY <= minRightX) {

                // Even length
                if ((x + y) % 2 == 0) {

                    return (
                            Math.max(maxLeftX, maxLeftY)
                            +
                            Math.min(minRightX, minRightY)
                    ) / 2.0;
                }

                // Odd length
                else {
                    return Math.max(maxLeftX, maxLeftY);
                }
            }

            // Left side bada hai
            else if (maxLeftX > minRightY) {
                high = partitionX - 1;
            }

            // Right move karo
            else {
                low = partitionX + 1;
            }
        }

        return 0.0;
    }

    public static void main(String[] args) {

        MedianFinder obj = new MedianFinder();

        int[] nums1 = {1, 2};
        int[] nums2 = {3, 4};

        double ans = obj.findMedianSortedArrays(nums1, nums2);

        System.out.println("Median = " + ans);
    }
}