Median of Two Sorted Arrays in Python and Java Using Binary Search

What Is the Median?

The median is the middle value of a sorted list. If the total number of elements is odd, the median is the middle element. If the total number of elements is even, the median is the average of the two middle elements.

Example 1:
Numbers: [1, 4, 5, 6, 233]
Median: 5

Example 2:
Numbers: [1, 2, 3, 4]
Median: (2 + 3) / 2 = 2.5

Problem Example

Suppose we have two sorted arrays:

nums1 = [1, 233]
nums2 = [4, 5, 6]

If we combine them mentally, the sorted order becomes:

[1, 4, 5, 6, 233]

There are five numbers, so the median is the third number: 5.

Why Binary Search Is Better Than Merging

Merging both arrays works, but it takes more time because we must process all values. The optimized method finds the correct middle position without merging the arrays.

• Merge solution: O(m + n)
• Binary search solution: O(log(min(m, n)))
• Space complexity: O(1)

This makes binary search much better when the arrays are large.

Watch the Video

Watch on YouTube: https://youtu.be/Qqc0x0lDCdQ

Main Idea of the Algorithm

We split both arrays into two parts: a left side and a right side. The goal is to make sure all values on the left side are smaller than or equal to all values on the right side.

Left side                Right side
[ smaller values ]   |   [ larger values ]

Once this correct partition is found, the median is available from the boundary values near the split.

Important Partition Rule

The partition is correct when these two conditions are true:

left value of first array <= right value of second array

left value of second array <= right value of first array

In code, we write it like this:

if firstLeft <= secondRight and secondLeft <= firstRight:
    # correct partition found

Python Solution

This Python version uses clear class and function names. It always applies binary search on the smaller array.

class MedianArrayCalculator:
    def find_median(self, first_numbers, second_numbers):
        # Binary search should happen on the smaller array
        if len(first_numbers) > len(second_numbers):
            first_numbers, second_numbers = second_numbers, first_numbers

        first_length = len(first_numbers)
        second_length = len(second_numbers)

        total_length = first_length + second_length
        left_side_size = (total_length + 1) // 2

        low = 0
        high = first_length

        while low <= high:
            first_cut = (low + high) // 2
            second_cut = left_side_size - first_cut

            first_left = float("-inf") if first_cut == 0 else first_numbers[first_cut - 1]
            first_right = float("inf") if first_cut == first_length else first_numbers[first_cut]

            second_left = float("-inf") if second_cut == 0 else second_numbers[second_cut - 1]
            second_right = float("inf") if second_cut == second_length else second_numbers[second_cut]

            # Correct partition
            if first_left <= second_right and second_left <= first_right:
                if total_length % 2 == 1:
                    return max(first_left, second_left)

                return (
                    max(first_left, second_left) +
                    min(first_right, second_right)
                ) / 2

            # Move partition left
            if first_left > second_right:
                high = first_cut - 1

            # Move partition right
            else:
                low = first_cut + 1


# Example usage
first_numbers = [1, 233]
second_numbers = [4, 5, 6]

calculator = MedianArrayCalculator()
result = calculator.find_median(first_numbers, second_numbers)

print(result)

Java Solution

The Java version follows the same logic. Instead of Python infinity values, we use Integer.MIN_VALUE and Integer.MAX_VALUE to handle edge partitions.

class MedianArrayCalculator {
    public double findMedian(int[] firstNumbers, int[] secondNumbers) {
        // Binary search should happen on the smaller array
        if (firstNumbers.length > secondNumbers.length) {
            return findMedian(secondNumbers, firstNumbers);
        }

        int firstLength = firstNumbers.length;
        int secondLength = secondNumbers.length;

        int totalLength = firstLength + secondLength;
        int leftSideSize = (totalLength + 1) / 2;

        int low = 0;
        int high = firstLength;

        while (low <= high) {
            int firstCut = (low + high) / 2;
            int secondCut = leftSideSize - firstCut;

            int firstLeft = firstCut == 0
                ? Integer.MIN_VALUE
                : firstNumbers[firstCut - 1];

            int firstRight = firstCut == firstLength
                ? Integer.MAX_VALUE
                : firstNumbers[firstCut];

            int secondLeft = secondCut == 0
                ? Integer.MIN_VALUE
                : secondNumbers[secondCut - 1];

            int secondRight = secondCut == secondLength
                ? Integer.MAX_VALUE
                : secondNumbers[secondCut];

            // Correct partition
            if (firstLeft <= secondRight && secondLeft <= firstRight) {
                if (totalLength % 2 == 1) {
                    return Math.max(firstLeft, secondLeft);
                }

                return (
                    Math.max(firstLeft, secondLeft) +
                    Math.min(firstRight, secondRight)
                ) / 2.0;
            }

            // Move partition left
            if (firstLeft > secondRight) {
                high = firstCut - 1;
            }

            // Move partition right
            else {
                low = firstCut + 1;
            }
        }

        return 0.0;
    }

    public static void main(String[] args) {
        int[] firstNumbers = {1, 233};
        int[] secondNumbers = {4, 5, 6};

        MedianArrayCalculator calculator = new MedianArrayCalculator();
        double result = calculator.findMedian(firstNumbers, secondNumbers);

        System.out.println(result);
    }
}

Step-by-Step Explanation

Step 1: Use the Smaller Array

We search only the smaller array. This keeps the binary search short and avoids invalid partition positions.

Step 2: Find the Left Side Size

The left side must contain half of the total elements. We use (total + 1) / 2 so that odd-length cases keep the extra value on the left side.

Step 3: Choose Two Cut Positions

Binary search chooses the cut position in the first array. The cut position in the second array is calculated automatically.

firstCut + secondCut = leftSideSize

Step 4: Compare Border Values

We check the values near both cuts. The algorithm only needs four values:

• firstLeft
• firstRight
• secondLeft
• secondRight

Step 5: Return the Median

If the total number of elements is odd, return the larger value from the left side. If the total is even, return the average of the largest left value and the smallest right value.

Output for the Example

5

The combined sorted order is [1, 4, 5, 6, 233], so the median is 5.

Time and Space Complexity

• Time Complexity: O(log(min(m, n)))
• Space Complexity: O(1)

The algorithm is fast because it does not merge arrays. It only moves the partition until the correct middle position is found.

Key Points to Remember

• Both arrays must be sorted before using this method.
• Binary search should be applied to the smaller array.
• The left side should contain half of the total elements.
• The correct partition gives the median immediately.
• This solution avoids extra memory because it does not merge arrays.

Conclusion

The median of two sorted arrays problem looks difficult at first, but the partition idea makes it easier. Instead of merging arrays, we use binary search to find the correct split point.

This method works efficiently in both Python and Java and is a strong example of using binary search for optimized problem solving.