Example: Median of Two Sorted Arrays - Binary Search in Java

// Median of Two Sorted Arrays - Binary Search
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // Example 1
        int[] nums1_ex1 = {1, 3};
        int[] nums2_ex1 = {2};
        System.out.println("Input: nums1=" + Arrays.toString(nums1_ex1) + ", nums2=" + Arrays.toString(nums2_ex1));
        System.out.println("Median (Binary Search): " + findMedianSortedArraysBinarySearch(nums1_ex1, nums2_ex1)); // Expected: 2.0

        // Example 2
        int[] nums1_ex2 = {1, 2};
        int[] nums2_ex2 = {3, 4};
        System.out.println("Input: nums1=" + Arrays.toString(nums1_ex2) + ", nums2=" + Arrays.toString(nums2_ex2));
        System.out.println("Median (Binary Search): " + findMedianSortedArraysBinarySearch(nums1_ex2, nums2_ex2)); // Expected: 2.5

        // Example 3: Empty array
        int[] nums1_ex3 = {};
        int[] nums2_ex3 = {1};
        System.out.println("Input: nums1=" + Arrays.toString(nums1_ex3) + ", nums2=" + Arrays.toString(nums2_ex3));
        System.out.println("Median (Binary Search): " + findMedianSortedArraysBinarySearch(nums1_ex3, nums2_ex3)); // Expected: 1.0

        // Example 4: More complex
        int[] nums1_ex4 = {1, 2, 5};
        int[] nums2_ex4 = {3, 4, 6, 7, 8};
        System.out.println("Input: nums1=" + Arrays.toString(nums1_ex4) + ", nums2=" + Arrays.toString(nums2_ex4));
        System.out.println("Median (Binary Search): " + findMedianSortedArraysBinarySearch(nums1_ex4, nums2_ex4)); // Expected: 4.5
    }

    public static double findMedianSortedArraysBinarySearch(int[] nums1, int[] nums2) {
        // Step 1: Ensure nums1 is the shorter array for binary search efficiency.
        // This simplifies logic by always performing binary search on the smaller array.
        if (nums1.length > nums2.length) {
            return findMedianSortedArraysBinarySearch(nums2, nums1);
        }

        int m = nums1.length;
        int n = nums2.length;

        // Step 2: Define the range for the binary search on nums1's partition point.
        // 'low' represents 0 elements taken from nums1 (all from nums2)
        // 'high' represents all elements taken from nums1 (0 from nums2)
        int low = 0;
        int high = m;

        // Step 3: Calculate the required number of elements in the left half of the combined array.
        // This handles both odd and even total lengths correctly for partition calculation.
        int halfLen = (m + n + 1) / 2;

        // Step 4: Perform binary search to find the correct partition
        while (low <= high) {
            // 'partitionX' is the number of elements taken from nums1 for the left half
            int partitionX = (low + high) / 2;
            // 'partitionY' is the number of elements taken from nums2 for the left half
            int partitionY = halfLen - partitionX;

            // Step 5: Determine the maximum element on the left side and minimum on the right side
            // Handle edge cases where a partition is at the beginning (0 elements) or end (all elements)
            int maxX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minX = (partitionX == m) ? Integer.MAX_VALUE : nums1[partitionX];

            int maxY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minY = (partitionY == n) ? Integer.MAX_VALUE : nums2[partitionY];

            // Step 6: Check if the partitions are correct
            if (maxX <= minY && maxY <= minX) {
                // Correct partition found. The elements are correctly divided.
                // Now determine the median based on total length.
                if ((m + n) % 2 == 1) {
                    // Total length is odd, median is the maximum of the left half
                    return (double) Math.max(maxX, maxY);
                } else {
                    // Total length is even, median is the average of the two middle elements
                    return (double) (Math.max(maxX, maxY) + Math.min(minX, minY)) / 2.0;
                }
            } else if (maxX > minY) {
                // We have taken too many elements from nums1 (maxX is too large),
                // need to move partitionX to the left in nums1.
                high = partitionX - 1;
            } else { // maxY > minX
                // We have taken too few elements from nums1 (maxY is too large, implying minX is too small),
                // need to move partitionX to the right in nums1.
                low = partitionX + 1;
            }
        }

        // This line should theoretically not be reached if the inputs are valid sorted arrays.
        // It indicates an error condition.
        throw new IllegalArgumentException("Input arrays are not sorted or invalid.");
    }
}