Median of Two Sorted Arrays: Brute Force and Binary Search

Finding the median of two sorted arrays is one of the few problems with a naive O(m+n) solution and an optimal O(log(min(m,n))) solution where both approaches matter in practice.

The naive merge works for most settings. The binary search partition is what interviewers at product companies want to see. This article covers both, with verified code and worked examples.

What Is the Median of Two Sorted Arrays?

The median of a single sorted array is the middle element. For an odd-length array, that’s the element at the centre. For an even-length array, it’s the average of the two central elements.

Two examples to fix the definition:

• Array [2, 7, 9, 11, 16] has length 5 (odd). Median = element at index 2 = 9.
• Array [1, 2, 3, 4, 5, 6] has length 6 (even). Median = average of index 2 and index 3 = (3 + 4) / 2 = 3.5.

For two sorted arrays, the definition extends: treat the combined sorted sequence as one array and find its median. The combined array is never explicitly constructed in the optimal solution.

The combined length m + n determines which case applies:

• Odd combined length: the median is the single middle element at position (m+n)//2 in the merged order (0-indexed).
• Even combined length: the median is the average of the elements at positions (m+n)//2 - 1 and (m+n)//2.

The partition-based approach exploits one further observation: to find the median, you only need to find the correct split point. You don’t need to build the merged array. Specifically, split both arrays so the combined left half contains exactly (m+n+1)//2 elements, and every element on the left side is at most every element on the right side. Once that split is found, the median follows directly from the two boundary values.

Brute Force: Merge and Find the Middle

The straightforward approach uses the two-pointer merge step from merge sort. Walk through both arrays simultaneously, collecting elements in order, then read the median from the centre.

def median_brute(nums1, nums2):
    """Merge both sorted arrays, then return the median.
    Time: O(m+n).  Space: O(m+n).
    """
    merged = []
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1
        else:
            merged.append(nums2[j])
            j += 1
    # Append any remaining elements from either array.
    merged.extend(nums1[i:])
    merged.extend(nums2[j:])

    n = len(merged)
    if n % 2 == 1:
        return merged[n // 2]
    else:
        return (merged[n // 2 - 1] + merged[n // 2]) / 2

The merge step runs in O(m+n) time, one comparison per element. The median read is O(1). Total time: O(m+n). Total space: O(m+n) for the merged array.

This approach is correct and simple to implement under interview pressure. The practical limitation is memory: allocating an O(m+n) array is wasteful when only two values from the centre are needed. For arrays of millions of elements, the binary search approach below avoids this entirely.

A simpler one-liner that also works, at the cost of losing the O(m+n) merge time (it sorts the concatenation instead):

def median_simple(nums1, nums2):
    combined = sorted(nums1 + nums2)
    n = len(combined)
    return combined[n // 2] if n % 2 == 1 else (combined[n // 2 - 1] + combined[n // 2]) / 2

Time: O((m+n) log(m+n)). Acceptable for interview whiteboard work; not acceptable if the interviewer specifies O(m+n) or better.

Binary Search Partition: O(log(min(m,n))) Solution

The binary search approach avoids building the merged array entirely. It searches directly for the partition point.

The Core Invariant

Split nums1 at index i and nums2 at index j. Define the left half as nums1[0..i-1] and nums2[0..j-1], and the right half as nums1[i..m-1] and nums2[j..n-1].

A partition is valid when two conditions hold simultaneously:

• Size condition: i + j == (m+n+1)//2. The combined left half has exactly the right number of elements.
• Order condition: nums1[i-1] <= nums2[j] AND nums2[j-1] <= nums1[i]. Every element on the left side doesn’t exceed every element on the right side.

Once a valid partition exists, the median values are:

• left_max = max(nums1[i-1], nums2[j-1]) (the largest element on the left side)
• right_min = min(nums1[i], nums2[j]) (the smallest element on the right side)
• If (m+n) is odd: median = left_max
• If (m+n) is even: median = (left_max + right_min) / 2

Adjusting the Partition

Binary search on i (the partition index in the smaller array). If nums2[j-1] > nums1[i], the left side of nums2 is too large, so move i right to compensate. If nums1[i-1] > nums2[j], the left side of nums1 is too large, so move i left.

Always keep nums1 as the smaller array. Swap if necessary before starting.

def median_binary_search(nums1, nums2):
    """Binary search partition for median of two sorted arrays.
    Time: O(log(min(m, n))).  Space: O(1).
    """
    # Ensure nums1 is the smaller array.
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    half_len = (m + n + 1) // 2
    lo, hi = 0, m

    while lo <= hi:
        i = (lo + hi) // 2
        j = half_len - i

        # Partition invalid: nums1's left side is too small. Move i right.
        if i < m and nums2[j - 1] > nums1[i]:
            lo = i + 1
        # Partition invalid: nums1's left side is too large. Move i left.
        elif i > 0 and nums1[i - 1] > nums2[j]:
            hi = i - 1
        else:
            # Valid partition found. Compute boundary values.
            if i == 0:
                left_max = nums2[j - 1]
            elif j == 0:
                left_max = nums1[i - 1]
            else:
                left_max = max(nums1[i - 1], nums2[j - 1])

            if (m + n) % 2 == 1:
                return left_max

            if i == m:
                right_min = nums2[j]
            elif j == n:
                right_min = nums1[i]
            else:
                right_min = min(nums1[i], nums2[j])

            return (left_max + right_min) / 2

The while lo <= hi loop runs at most log2(m+1) iterations. The binary search range is [0, m], so iteration count scales with the smaller array’s size, not the larger.

Boundary Conditions

The edge cases for left_max and right_min cover two scenarios: partition index at 0 (the array contributes nothing to the left half) and partition index at m or n (the entire array is on the left side). Using negative infinity as a sentinel for an empty left boundary and positive infinity for an empty right boundary makes the comparisons uniform, but the explicit checks above make the intent clearer.

Worked Examples Step by Step

These examples verify both approaches from first principles.

Example 1: Same-Size Arrays (the Legacy Test Case)

• Input: nums1 = [1, 12, 15, 26, 38], nums2 = [2, 13, 17, 30, 45]
• Step 1: Merge manually. Compare heads of each array in order:
  • Take 1, then 2, then 12, then 13, then 15, then 17, then 26, then 30, then 38, then 45.
• Step 2: Merged sequence: [1, 2, 12, 13, 15, 17, 26, 30, 38, 45]
• Step 3: Combined length = 10 (even). Middle indices: 4 and 5 (0-indexed).
• Step 4: Values at those indices: 15 and 17.
• Step 5: Median = (15 + 17) / 2 = 16.
• Answer: 16

Example 2: Different-Size Arrays

• Input: nums1 = [1, 3], nums2 = [2]
• Combined length = 3 (odd). Expected median: 2.
• After swap (because len([1,3]) > len([2])): nums1 = [2], nums2 = [1, 3].
• m = 1, n = 2, half_len = (1+2+1)//2 = 2.
• Binary search: lo = 0, hi = 1.
  • Iteration 1: i = 0, j = 2. Check: nums2[j-1] = nums2[1] = 3 > nums1[0] = 2. Move right: lo = 1.
  • Iteration 2: i = 1, j = 1. Check: neither condition triggers.
  • Valid partition. left_max = max(nums1[0], nums2[0]) = max(2, 1) = 2.
  • (m+n) = 3 is odd. Return left_max = 2.
• Answer: 2 (correct)

Example 3: One Array Empty

• Input: nums1 = [], nums2 = [1, 2, 3, 4]
• m = 0, n = 4, half_len = (0+4+1)//2 = 2.
• Binary search: lo = 0, hi = 0.
  • Iteration 1: i = 0, j = 2. No conditions trigger (i is not < m; i is not > 0).
  • Valid partition. i == 0, so left_max = nums2[j-1] = nums2[1] = 2.
  • (m+n) = 4 is even. i == m, so right_min = nums2[j] = nums2[2] = 3.
  • Return (2 + 3) / 2 = 2.5.
• Answer: 2.5 (correct; median of [1, 2, 3, 4] is 2.5)

Approach Comparison

Approach	Time	Space	When to use
Simple sort (sorted)	O((m+n) log(m+n))	O(m+n)	Quick prototyping, small arrays
Two-pointer merge	O(m+n)	O(m+n)	When O(m+n) is acceptable
Binary search partition	O(log(min(m,n)))	O(1)	Interview expectation, large arrays

The binary search partition is harder to implement correctly under pressure, but it’s the solution that demonstrates depth of understanding. If an interviewer says “can you do better than O(m+n)?”, this is the only path available.

Where This Problem Appears in Placements

LeetCode Problem 4 (Hard) is the canonical version of this question. The original FACE Prep article on this topic cited PayPal and Flipkart as companies that have used it in recruitment drives. It’s an interview-round question, not a component of standard campus aptitude tests like AMCAT, CoCubes, or TCS NQT.

What makes it useful as an interview question is the contrast between a correct naive solution and a more efficient one. Knowing the merge approach shows competence with arrays. Knowing the binary search partition shows the ability to recognise and exploit problem structure, specifically the insight that you can find the median without constructing the merged array, because the median is fully determined by the boundary values of the correct partition.

The GeeksforGeeks explanation of this algorithm includes the mathematical proof that the partition invariant is both necessary and sufficient, useful if you want to verify why the binary search converges to the correct answer.

Preparation for campus placement evaluation tests covers the aptitude round that precedes the coding interview. For broader placement preparation resources covering both aptitude and data structures, strong quantitative aptitude practice builds the mathematical reasoning that transfers to algorithm analysis.

The binary search partition works because you hold two simultaneous constraints across two sequences and verify them at each step. That discipline of systematic constraint checking is also what separates well-engineered AI prompts from ones that drift. If the partition logic clicked here, TinkerLLM is where the same kind of structured thinking gets applied to language models, starting at ₹499.