Median of Two Sorted Arrays

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Given two sorted arrays of sizes m and n, return the median of all their numbers combined, in O(log(min(m, n))) time. With an odd total the median is the middle number; with an even total it is the average of the two middle numbers. Either array may be empty, but not both.

    The merge answer is easy, so the whole question is about the logarithmic bound. It is one of the best-known binary search problems because you don't search for a value: you search for a cut. Original problem: LeetCode 4.

    Example

    Merged, the seven numbers are 1 2 3 4 7 9 10, so the median is the 4th one: 4.
    Merged, the seven numbers are 1 2 3 4 7 9 10, so the median is the 4th one: 4.
    A = [1, 4, 9], B = [2, 3, 7, 10]
    Output: 4.0          # merged: 1 2 3 [4] 7 9 10
    A = [1, 4, 9], B = [2, 3, 7, 10, 12]
    Output: 5.5          # merged: 1 2 3 [4 7] 9 10 12 -> (4 + 7) / 2

    Constraints (assumed)

    • 0 ≤ m, n ≤ 1,000 and m + n ≥ 1.
    • Values fit in a 32-bit integer.

    What this question tests

    • Reframing "find the median" as "find a partition of both arrays".
    • A binary search on the answer's structure, with exact conditions for moving left or right.
    • Handling empty sides and odd/even totals without special-case spaghetti.

    Questions to ask first

    1. Can either array be empty? (Here: yes, one of them.)
    2. Are there duplicates, and can they cross arrays? (Yes; the method doesn't care.)
    3. What should an even total return? The average, as a float.
    4. Is O(m + n) acceptable? If yes, a two-pointer merge is enough; the expected answer is logarithmic.