Median of two sorted arrays in O(log(min(m,n))) — how does the partition trick work?

Q: Median of two sorted arrays in O(log(min(m,n))) — how does the partition trick work?

**Target Audience:** Intermediate interview candidates — you should know binary search and what a sorted array is; every other idea is explained here. **Difficulty:** Hard **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output, step count and ordering claim below was produced by actually running the Python programs in the **Verified** section. ## 1. Why This Even Matters — A Story First Two schools line up their students by height for a joint photo — each line is already sorted, shortest to tallest. The photographer wants the **middle** height of all the students together. The obvious way: merge the two lines into one long sorted line and walk to the middle. That works, but if the lines are a million students long, you walk past half a million people. The clever way: the photographer does not need the merged line, only a **dividin

The problem

Question presented to candidate: "You have two sorted lists of integers, of lengths m and n. Return the median of all the numbers together. A merge is O(m + n); I would like O(log(min(m, n))). Please write it in Python and explain the partition idea."

What a strong answer should cover:

The merge baseline in O(m + n), then the observation that choosing a cut i in one list forces j = half - i in the other.
The validity test A[i-1] <= B[j] and B[j-1] <= A[i], with infinities at the edges, and how each failure says which way to move.
Binary search on i over the shorter list: O(log(min(m, n))) time, O(1) space, and why it keeps j in range.
Reading the median from the cut for odd and even totals.
Python specifics: float('inf') sentinels, // for half, / returning a float for the even case, unbounded int, and that statistics.median(a + b) is an O((m+n) log(m+n)) shortcut, not the answer.

Clarifying questions expected:

"Can either list be empty?"
"For an even total, do you want the average of the two middle values?"

Code / implementation expected: Yes — find_median_sorted_arrays(a, b) in Python using the partition binary search.

binary search
array
Amazon

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Intermediate interview candidates — you should know binary search and what a sorted array is; every other idea is explained here. Difficulty: Hard Language: Python 3

How to read this doc: Each idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output, step count and ordering claim below was produced by actually running the Python programs in the Verified section.

1. Why This Even Matters — A Story First

Two schools line up their students by height for a joint photo — each line is already sorted, shortest to tallest. The photographer wants the middle height of all the students together.

The obvious way: merge the two lines into one long sorted line and walk to the middle. That works, but if the lines are a million students long, you walk past half

The solution is hidden so you can try first

11 min read · 13 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonThe partition search on eight inputs, including empty and negative arrays

Practice

PythonTrace of the cuts, plus 500 random tests against the merge

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.