Median of Two Sorted Arrays: Binary Search on Partitions

LeetCode 4. It's the absolute classic interview question that makes candidates sweat, panic, and suddenly forget how to write a basic while loop.

If you're interviewing for an L4/L5 role at Google, Meta, or Amazon, this is the exact kind of problem they drop on you to see if you can handle high-pressure optimization. The brute force solution takes about three minutes to code. The optimized solution? It requires fundamentally rewiring how you think about binary search.

We are not going to search for a specific number today. We are going to search for a cut.

Most people try to memorize the code for this problem. That's a massive footgun. You will forget a + 1, mess up an index, and crash and burn. Instead, we are going to understand the underlying math of partitions so deeply that you can derive the code from scratch on a whiteboard.

The Core Concept: Searching for a Cut

Before we write a single line of code, we need to talk about what a median actually is.

In statistics, a median divides a dataset into two equal halves. The left half contains all the smaller numbers. The right half contains all the larger numbers. If the total number of elements is odd, the median is exactly in the middle. If it's even, the median is the average of the two middle elements.

When you have two sorted arrays, nums1 and nums2, your goal isn't to build a new merged array. Your goal is to draw a line—a cut—through both arrays such that:

1. The total number of elements on the left side of the cuts equals the total number of elements on the right side.
2. Every single element on the left side is less than or equal to every single element on the right side.

If we can find those exact cut points, we have our median. The maximum element on the left side and the minimum element on the right side give us the answer immediately. No merging required.

The Brute Force Approaches

Before we get to the $O(\log(\min(m,n)))$ magic, we need to acknowledge the brute force. Interviewers almost always ask you to explain the naive approach first. Don't skip this. It shows you understand the baseline.

1. The Naive Merge — $O(m+n)$ Time and Space

The most obvious solution is to merge the two arrays into a single sorted array and pick the middle element. It's essentially the merge step of Merge Sort.

function findMedianSortedArraysNaive(nums1: number[], nums2: number[]): number {
    const merged: number[] = [];
    let i = 0;
    let j = 0;
 
    // Standard merge operation
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            merged.push(nums1[i]);
            i++;
        } else {
            merged.push(nums2[j]);
            j++;
        }
    }
 
    // Dump remaining elements
    while (i < nums1.length) merged.push(nums1[i++]);
    while (j < nums2.length) merged.push(nums2[j++]);
 
    const totalLen = merged.length;
    const mid = Math.floor(totalLen / 2);
 
    if (totalLen % 2 === 0) {
        return (merged[mid - 1] + merged[mid]) / 2;
    } else {
        return merged[mid];
    }
}

This works. It's clean. But it fails the strict $O(\log(m+n))$ constraint of the problem. It requires $O(m+n)$ auxiliary space to hold the merged array.

2. The Optimized Brute Force — $O(m+n)$ Time, $O(1)$ Space

A solid interviewer will immediately say: "Good. Now, can you do it without creating a new array?"

You don't need the whole array. You only need the middle one or two elements. We can maintain two pointers and a counter, traversing the arrays exactly as we did above, but without storing the result. We just keep track of the current and previous values as we step forward.

function findMedianSortedArraysBetter(nums1: number[], nums2: number[]): number {
    const totalLen = nums1.length + nums2.length;
    const targetIndex = Math.floor(totalLen / 2);
    
    let i = 0;
    let j = 0;
    let current = 0;
    let previous = 0;
 
    for (let count = 0; count <= targetIndex; count++) {
        previous = current;
        
        // If nums1 is exhausted, pick from nums2
        if (i === nums1.length) {
            current = nums2[j];
            j++;
        } 
        // If nums2 is exhausted, pick from nums1
        else if (j === nums2.length) {
            current = nums1[i];
            i++;
        } 
        // Otherwise, pick the smaller element
        else if (nums1[i] < nums2[j]) {
            current = nums1[i];
            i++;
        } else {
            current = nums2[j];
            j++;
        }
    }
 
    if (totalLen % 2 === 0) {
        return (previous + current) / 2;
    } else {
        return current;
    }
}

This is better. The space complexity is down to $O(1)$. But we are still linear. If both arrays have 10 million elements, we are iterating 10 million times. We need logarithmic time. That means Binary Search.

The Optimized Solution: Binary Search on Partitions

Let's break this down. We have two arrays: nums1 of length x and nums2 of length y.

We need to partition both arrays. Let's call the cut points partitionX and partitionY.

Handling the Edge Cases (The Infinities)

So here's the thing. What happens if the cut is at the very beginning of the array? It means there are zero elements on the left side of that array. What is maxLeft then?

If we try to access index -1, JavaScript gives us undefined. In typed languages like Java or C++, it throws an IndexOutOfBoundsException.

This makes the math work flawlessly without writing ten different conditional statements. -Infinity is always smaller than minRight, and Infinity is always larger than maxLeft.

Moving the Binary Search Pointers

What if our cuts aren't right? We have to shift our search space.

If maxLeftX > minRightY, it means we pulled too many large numbers from nums1 into the left half. Our partitionX is too far to the right. We need to move it left. Action: high = partitionX - 1

If maxLeftY > minRightX, it means we pulled too many large numbers from nums2 into the left half. We need more numbers from nums1 on the left. Our partitionX is too far left. Action: low = partitionX + 1

The Final Optimized Code

Read through this carefully. Notice how variables are named based on their physical location relative to the cut.

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    // 1. Always binary search on the smaller array to prevent out of bounds.
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }
 
    const x = nums1.length;
    const y = nums2.length;
    
    let low = 0;
    let high = x;
 
    while (low <= high) {
        // Find the cut point in nums1
        const partitionX = Math.floor((low + high) / 2);
        
        // Deduce the cut point in nums2
        const partitionY = Math.floor((x + y + 1) / 2) - partitionX;
 
        // Find the 4 elements bordering the cuts. 
        // Handle edges using Infinity / -Infinity
        const maxLeftX = partitionX === 0 ? -Infinity : nums1[partitionX - 1];
        const minRightX = partitionX === x ? Infinity : nums1[partitionX];
 
        const maxLeftY = partitionY === 0 ? -Infinity : nums2[partitionY - 1];
        const minRightY = partitionY === y ? Infinity : nums2[partitionY];
 
        // Check if we found the valid partitions
        if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
            
            // We found it. Now calculate median based on odd/even total length.
            // If total length is odd, the extra element is on the left side.
            if ((x + y) % 2 !== 0) {
                return Math.max(maxLeftX, maxLeftY);
            } 
            // If total length is even, it's the average of the largest left
            // and the smallest right.
            else {
                return (Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
            }
 
        } 
        // We are too far right in nums1. Move left.
        else if (maxLeftX > minRightY) {
            high = partitionX - 1;
        } 
        // We are too far left in nums1. Move right.
        else {
            low = partitionX + 1;
        }
    }
 
    throw new Error("Input arrays are not sorted.");
}

Dry Run: Visualizing the Cuts

Code is great, but walking through a nasty, asymmetrical example is how this actually clicks in your brain.

Let's use these arrays:

• X: [1, 3, 8, 9, 15] (Length x = 5)
• Y: [7, 11, 18, 19, 21, 25] (Length y = 6)

Total length = 11. Half length = Math.floor((5 + 6 + 1) / 2) = 6. We need 6 elements on the left side.

Iteration 1

• low = 0, high = 5
• partitionX = Math.floor((0 + 5) / 2) = 2. Cut X after index 1.
• partitionY = 6 - 2 = 4. Cut Y after index 3.

Let's look at the elements around our cuts:

• Left X: [1, 3] -> maxLeftX = 3
• Right X: [8, 9, 15] -> minRightX = 8
• Left Y: [7, 11, 18, 19] -> maxLeftY = 19
• Right Y: [21, 25] -> minRightY = 21

Cross check:

1. maxLeftX (3) <= minRightY (21) -> True
2. maxLeftY (19) <= minRightX (8) -> False

Update pointers: low = partitionX + 1 = 2 + 1 = 3.

Iteration 2

• low = 3, high = 5
• partitionX = Math.floor((3 + 5) / 2) = 4. Cut X after index 3.
• partitionY = 6 - 4 = 2. Cut Y after index 1.

Let's look at the elements around the new cuts:

• Left X: [1, 3, 8, 9] -> maxLeftX = 9
• Right X: [15] -> minRightX = 15
• Left Y: [7, 11] -> maxLeftY = 11
• Right Y: [18, 19, 21, 25] -> minRightY = 18

Cross check:

1. maxLeftX (9) <= minRightY (18) -> True
2. maxLeftY (11) <= minRightX (15) -> True

Boom. Valid partitions found.

Since total length is 11 (odd), the median is just the largest element on the left side. Math.max(maxLeftX, maxLeftY) -> Math.max(9, 11) = 11.

If we merged the arrays manually, they would look like this: [1, 3, 7, 8, 9, 11, 15, 18, 19, 21, 25]. The 6th element is indeed 11. The math perfectly maps to reality.

Complexity Analysis

Let's compare the three approaches we covered.

Why is the time complexity $O(\log(\min(m, n)))$ and not $O(\log(m + n))$?

Because we intentionally force the binary search to happen strictly on the smaller array. If m is 10 and n is 1,000,000, we do a binary search on the array of size 10. That's roughly 4 iterations. If we searched the larger array, it would take roughly 20 iterations. Furthermore, searching the larger array breaks our partition bounds math.

Variations of the Pattern

Once you grasp "binary searching a partition," you can solve a whole class of hard array problems.

K-th Element of Two Sorted Arrays

Instead of looking for the median, you are asked to find the $k$-th smallest element in two sorted arrays.

The adjustment: It's exactly the same algorithm. The only difference is how you define the target left side size. Instead of Math.floor((x + y + 1) / 2), your target left side size is exactly k. You run the binary search on the smaller array, ensuring partitionX + partitionY = k. When you find the valid cuts, the answer is Math.max(maxLeftX, maxLeftY).

Median of Row-Wise Sorted Matrix

Finding the median of a matrix where every row is sorted. You can't partition the matrix easily, but you can use binary search on the value range (from the matrix's global minimum to maximum) and use upper_bound logic to count how many elements are smaller than your mid value. It uses the exact same core concept: finding a line that divides the data perfectly in half based on constraints.

Check Your Understanding

Interview Tips & Common Mistakes

When I interview candidates with this problem, I'm rarely looking for them to drop the perfect syntax on the first try. It's a complex algorithm with a lot of moving parts. Here is what separates strong candidates from weak ones.

1. Explaining the invariant before coding Do not touch the keyboard until you have drawn the arrays, drawn the cut lines, and written out maxLeftX <= minRightY and maxLeftY <= minRightX. If you start coding before you establish that logic, I assume you're reciting memorized code, and I will grill you heavily on edge cases.

2. Handling odd vs even lengths A common footgun is getting the median calculation wrong at the very end. Write down a tiny example like total length = 3 and total length = 4 on the whiteboard.

• Length 3: Target left side is (3+1)/2 = 2. The left side has 2 items, right side has 1. The median is the largest of the 2 left items.
• Length 4: Target left side is (4+1)/2 = 2. Left has 2, right has 2. The median is the average of max(Left) and min(Right).

3. The Infinity Trick If you write huge if/else blocks to handle partitionX === 0, it clutters your logic and makes it impossible to read. Show me the -Infinity/Infinity trick. It proves you understand why the edge case exists (empty partitions don't constrain the opposite array) rather than just patching an index out of bounds error.

4. Communicating through the panic You will likely get a variable mixed up. You'll type minRightX when you meant maxLeftY. That's normal. If you write your code cleanly and step through a dry run on the whiteboard like we did above, you will catch your own error. Self-correction is highly valued. If your code fails a test case and you blindly start changing +1 to -1 hoping it fixes it, that's a massive red flag.

Stop. Breathe. Draw the cut. Look at the numbers. The math won't lie to you.