LeetCode 4 · Binary Search

Median of Two Sorted Arrays, explained with a picture

Cutting two sorted shelves in half together.

HardBinary Search
▶ Watch it step by step

The problem

Given two sorted lists, find the median of all their numbers combined, in O(log(m + n)) time.

Input:  A = [1, 3, 8, 9, 15], B = [7, 11, 18, 19, 21, 25]
Output: 11

Picture it

Picture two sorted bookshelves. The median splits all books into a smaller half and a larger half. We make one cut in each shelf so that the left pieces together hold exactly half the books. The cut is right when every book left of both cuts is ≤ every book right of both cuts. We binary search where to cut the shorter shelf; the other cut follows automatically.

How to recognise it

  • Two lists are already sorted and you need an order statistic (the median, or the k-th smallest) of their combination.
  • The required time is O(log(m + n)), which rules out merging the lists, even though merging is easy.
  • The median splits the combined numbers into a left half and a right half of known sizes. Choosing how many items come from the first list decides how many come from the second, so there is only one number to search for: the cut position in the shorter list.

Start with brute force

Combine the lists, sort, and read the middle.

def median_brute(a, b):
    c = sorted(a + b)
    k = len(c)
    if k % 2:
        return c[k // 2]
    return (c[k // 2 - 1] + c[k // 2]) / 2

This is O((m + n) log(m + n)) time and O(m + n) space; a two-pointer merge brings it to O(m + n). With at most 1,000 numbers per list it runs instantly, but the problem asks for logarithmic time: about log2(1,000) ≈ 10 cut positions need checking, not 2,000 items.

From brute force to the idea

  1. Find the waste. To find the middle you only need to know where the halves split, not the full merged order.
  2. Cut both lists. Take i items from a and j from b for the left half. The left half must have half = (m + n + 1) // 2 items, so j = half - i. The + 1 puts the extra item on the left when the total is odd.
  3. Check the cut with four values. The cut is correct when every left item is at most every right item. Each list is sorted, so only the edges matter: a_left <= b_right and b_left <= a_right. A missing edge (cut at the very start or end) counts as -inf or inf.
  4. Move the cut. If a_left > b_right, too many items came from a: hi = i - 1. Otherwise b_left > a_right, so too few came from a: lo = i + 1.
  5. Read the median. For an odd total it is the largest left item, max(a_left, b_left). For an even total it is the average of that and the smallest right item.
  6. Search the shorter list. The first lines swap so that a is shorter. Then j = half - i always stays between 0 and n.

This is the key idea: binary search the cut position in the shorter list, and check it using the four values next to the two cuts.

The key idea

Binary search a partition of the shorter list; check maxLeft ≤ minRight on both sides. O(log(min(m, n))).

Python solution

def median(a, b):
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    lo, hi, half = 0, m, (m + n + 1) // 2
    while lo <= hi:
        i = (lo + hi) // 2             # cut in a
        j = half - i                   # matching cut in b
        a_left = a[i - 1] if i > 0 else -inf
        a_right = a[i] if i < m else inf
        b_left = b[j - 1] if j > 0 else -inf
        b_right = b[j] if j < n else inf
        if a_left <= b_right and b_left <= a_right:
            if (m + n) % 2:
                return max(a_left, b_left)
            return (max(a_left, b_left) + min(a_right, b_right)) / 2
        if a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO((m + n) log(m + n)) with sorting, O(m + n) with a mergeO(m + n): the combined list
Partition search (shown code)O(log min(m, n)): the cut range in the shorter list halves each stepO(1): a few numbers

Edge cases

  • Imports: the shown code uses inf without importing it, so it needs from math import inf; otherwise the first comparison raises NameError.
  • The example: returns 11.
  • One list empty ([] and [2, 3]): a is empty, i is 0, and the result is 2.5.
  • Return type: an odd total returns an element as is (an int for integer input, such as 11), and an even total returns a float. LeetCode accepts both.
  • All equal ([2, 2] and [2, 2]): the first cut is already valid; returns 2.0.
  • Both lists empty: the problem rules this out. The shown code would compute (-inf + inf) / 2 and return nan.

Common mistakes

  • Skipping the swap. With a longer, j can go negative, and Python's negative indexing reads from the end of b instead of failing.
  • Using half = (m + n) // 2 but still returning the left maximum for an odd total. For [1, 3] and [2] the median then comes out as 1 instead of 2.
  • Forgetting the -inf and inf guards, so a cut at either end of a list raises IndexError.
Your turn: the k-th smallest

Return the k-th smallest number (k counts from 1) of the two sorted lists combined, in O(log min(m, n)). For [1, 3, 8] and [2, 4] with k = 4 the answer is 4. Describe your approach, then write it if you like.

Compare with our answer

Use the same cut, but the left part now has exactly k items, so j = k - i. The cut in a must also leave j between 0 and n, which bounds the range: lo = max(0, k - n) and hi = min(k, m). The answer is the largest item on the left.

from math import inf

def kth(a, b, k):                  # k counts from 1
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    lo, hi = max(0, k - n), min(k, m)
    while lo <= hi:
        i = (lo + hi) // 2
        j = k - i
        a_left = a[i - 1] if i > 0 else -inf
        a_right = a[i] if i < m else inf
        b_left = b[j - 1] if j > 0 else -inf
        b_right = b[j] if j < n else inf
        if a_left <= b_right and b_left <= a_right:
            return max(a_left, b_left)
        if a_left > b_right:
            hi = i - 1
        else:
            lo = i + 1

The median is then kth of the middle position (or the average of the two middle positions).

A strong answer mentions: why the range for i must be clipped to max(0, k - n)..min(k, m), that the answer is the left maximum, and the O(log min(m, n)) cost.

Check what stuck

1. Two servers each keep a sorted list of response times, and you need the 90th-percentile time across both. Which approach fits best?

2. Why does the shown code use half = (m + n + 1) // 2 for the left half?

3. A learner deletes the first two lines that swap a and b. Which call now returns a wrong answer?

Score 60% or more and the lesson is marked complete.