Median of two sorted arrays

Why this matters

The median is the middle value of a set of numbers. It is a common measure in data work because it is not moved much by a few very large or very small values. Finding the median of one sorted list is easy, because you read the middle position. Finding the median of two sorted lists together is a classic interview problem, and it teaches a search method that is useful well beyond medians.

The obvious method merges the two lists into one sorted list and reads the middle. That takes time proportional to the total size of both lists. This lesson builds a faster method, which runs in O(log(min(m, n))) time, where m and n are the two lengths. It does not merge anything. It uses binary search to find where to cut each list, so that the cuts split the combined values into two equal groups.

The idea is related to the binary search lessons earlier in this module. This lesson assumes you already know how to halve a range until the answer is found.

What the median is

The median of a list is the value in the middle after sorting. If the list has an odd number of values, the median is the single middle value. If the list has an even number of values, the median is the average of the two middle values.

Here are three small examples.

1 2 3 has median 2.
1 2 3 4 has median (2 + 3) / 2 = 2.5.
1 3 and 2 taken together are 1 2 3, so the median is 2.

The task is to find this median when the two input lists are each already sorted, and when they are kept separate. For example, 1 3 and 2 are two sorted lists, and the answer is 2 even though the two lists are never merged.

The slow method first

Merge the two sorted lists into one sorted list, using the merge step from the merge sort lesson. Then read the middle value or the two middle values. If the lists have lengths m and n, the merge step takes m + n steps. This method is correct and easy to explain, but its time grows with the total size. For two lists of a million values each, it looks at two million values.

The faster method below does not look at most of the values. It needs only about log2(m) steps, where m is the length of the smaller list. For a million values in the smaller list, that is about 20 steps.

The big idea: cut both lists

Think of each sorted list as a row of numbers. Cut each row into a left part and a right part. A cut can be placed anywhere, including before the first value or after the last value.

Suppose the combined left parts hold exactly half of all values, and the combined right parts hold the other half. If every value on the left side is no larger than every value on the right side, then the median sits at the boundary between the two sides.

For an odd total, the median is the largest value on the left side.
For an even total, the median is the average of the largest value on the left side and the smallest value on the right side.

The search is now a search for cuts. Choose a cut in the first list, then choose a cut in the second list so that the left parts have the right number of values. Then check the boundary. If the largest left value of one list is bigger than the smallest right value of the other list, the first cut is too far right. Move it left. If not, move it right.

Choosing the cuts

Let the first list be a with length m, and the second list be b with length n. Let i be the number of values from a on the left side. The number of values from b on the left side must then be j = leftCount - i, where leftCount is the number of values the left side needs. For a total of m + n values, set leftCount to (m + n + 1) / 2. This works for both odd and even totals, and it puts the extra value on the left side when the total is odd.

Once i is chosen, j is fixed. Four values describe the boundary.

aLeft, the last value of a on the left side. If i is 0, there is no such value, so use the smallest possible int as a sentinel, which is a stand-in value for "no value here".
aRight, the first value of a on the right side. If i is m, there is no such value, so use the largest possible int.
bLeft, the last value of b on the left side. If j is 0, use the smallest possible int.
bRight, the first value of b on the right side. If j is n, use the largest possible int.

The cut is valid when aLeft <= bRight and bLeft <= aRight. Those two checks say that every value on the left side is no larger than every value on the right side. Because each list is sorted, these two checks are enough.

If the cut is not valid, there is one of two problems. If aLeft > bRight, the cut in a is too far right, so i must go down. Otherwise, bLeft > aRight, the cut in a is too far left, so i must go up. This is the step that makes the search a binary search.

Why search the smaller list

The value i runs from 0 to m. That range has m + 1 choices, so a binary search over it takes about log2(m + 1) steps. If a is the smaller list, that is the fastest choice.

There is a second reason to put the smaller list first. The count j = leftCount - i must stay between 0 and n for a valid index into b. When m is less than or equal to n, the value of leftCount - i stays in that range for every i from 0 to m. If the larger list were searched instead, j could fall below 0 or above n, and the program would read a value that does not exist.

So the code first swaps the two lists when a is longer than b. The swap does not change the median, because the median depends only on the values together.

Worked example 1: `1 3` and `2`

Here a is 1 3 with m = 2, and b is 2 with n = 1. The total is 3, so leftCount is (3 + 1) / 2 = 2. The search range for i is from 0 to 2.

Start with lo = 0 and hi = 2. The middle is i = 1, so j = 2 - 1 = 1.
aLeft is a[0], which is 1. aRight is a[1], which is 3.
bLeft is b[0], which is 2. bRight is past the end of b, so it is the largest int.
Check the cut. aLeft <= bRight is 1 <= large, which is true. bLeft <= aRight is 2 <= 3, which is true. The cut is valid.
The total is odd, so the median is the larger of the two left values, which is max(1, 2) = 2.

The left side holds 1 2 and the right side holds 3. The median is 2.

Worked example 2: `1 2` and `3 4`

Now the total is even, so the median is an average. Here m = n = 2 and leftCount is (4 + 1) / 2 = 2.

Start with lo = 0 and hi = 2. The middle is i = 1, so j = 1.
aLeft is 1, aRight is 2. bLeft is b[0], which is 3, and bRight is b[1], which is 4.
Check the cut. aLeft <= bRight is 1 <= 4, which is true. bLeft <= aRight is 3 <= 2, which is false. The cut is not valid.
Because the failure is bLeft > aRight, the cut in a is too far left, so set lo = i + 1 = 2.
The new middle is i = 2, so j = 0. Now aLeft is 2, aRight is the largest int because i equals m. bLeft is the smallest int because j is 0, and bRight is b[0], which is 3.
Check the cut. aLeft <= bRight is 2 <= 3, which is true. bLeft <= aRight is true, because the smallest int is at most anything. The cut is valid.
The total is even, so the median is the average of max(aLeft, bLeft) and min(aRight, bRight). That is (2 + 3) / 2 = 2.5.

The left side holds 1 2 and the right side holds 3 4, so the median is between 2 and 3.

Worked example 3: `-5 0 5 10` and `-3 8`

This example is harder for two reasons. The first list is longer than the second, so the code swaps the lists. The total is even.

After the swap, a is -3 8 with m = 2, and b is -5 0 5 10 with n = 4. The total is 6, so leftCount is (6 + 1) / 2 = 3.

Start with lo = 0 and hi = 2. The middle is i = 1, so j = 3 - 1 = 2.
aLeft is -3, aRight is 8. bLeft is b[1], which is 0, and bRight is b[2], which is 5.
Check the cut. aLeft <= bRight is -3 <= 5, which is true. bLeft <= aRight is 0 <= 8, which is true. The cut is valid on the first try.
The median is the average of max(-3, 0) = 0 and min(8, 5) = 5. That is (0 + 5) / 2 = 2.5.

Check by sorting all six values: -5 -3 0 5 8 10. The two middle values are 0 and 5, and their average is 2.5.

The C++ code

The program below has the search function and a main function with four examples. The search function is findMedianSortedArrays. It takes two spans, which are views of the two sorted vectors, and returns a double.

C++ · editable

#include <algorithm>
#include <climits>
#include <iostream>
#include <span>
#include <stdexcept>
#include <vector>

// Returns the median of two sorted arrays, taken together.
double findMedianSortedArrays(std::span<const int> a, std::span<const int> b) {
    if (a.size() > b.size()) {
        return findMedianSortedArrays(b, a);
    }
    const int m = static_cast<int>(a.size());
    const int n = static_cast<int>(b.size());
    const int total = m + n;
    const int leftCount = (total + 1) / 2;

int lo = 0;
    int hi = m;
    while (lo <= hi) {
        const int i = (lo + hi) / 2;
        const int j = leftCount - i;

const int aLeft = (i == 0) ? INT_MIN : a[i - 1];
        const int aRight = (i == m) ? INT_MAX : a[i];
        const int bLeft = (j == 0) ? INT_MIN : b[j - 1];
        const int bRight = (j == n) ? INT_MAX : b[j];

if (aLeft <= bRight && bLeft <= aRight) {
            if (total % 2 == 1) {
                return std::max(aLeft, bLeft);
            }
            return (static_cast<double>(std::max(aLeft, bLeft)) +
                    static_cast<double>(std::min(aRight, bRight))) / 2.0;
        }
        if (aLeft > bRight) {
            hi = i - 1;
        } else {
            lo = i + 1;
        }
    }
    throw std::invalid_argument("inputs are not sorted");
}

int main() {
    std::vector<int> a1 = {1, 3};
    std::vector<int> b1 = {2};
    std::vector<int> a2 = {1, 2};
    std::vector<int> b2 = {3, 4};
    std::vector<int> a3 = {};
    std::vector<int> b3 = {7, 9, 11};
    std::vector<int> a4 = {-5, 0, 5, 10};
    std::vector<int> b4 = {-3, 8};

std::cout << findMedianSortedArrays(a1, b1) << '\n';
    std::cout << findMedianSortedArrays(a2, b2) << '\n';
    std::cout << findMedianSortedArrays(a3, b3) << '\n';
    std::cout << findMedianSortedArrays(a4, b4) << '\n';
}

Compile and run it with these commands.

g++ -std=c++20 -Wall -Wextra -o median median.cpp
./median

The output is:

The four results match the hand traces. The third example has an empty first list. The empty list is the shorter one, so the code does not swap. The search runs on the empty list, with m = 0. The only cut is i = 0, so the median comes from the right list alone, which is 9 for 7 9 11.

A few details matter here.

std::span<const int> lets the function read both vectors without copying them. The caller passes a1 directly, and the vector converts to a span.
INT_MIN and INT_MAX come from <climits>. They stand in for "no value on this side", so the comparisons still work at the ends of the lists.
The average is computed in double. The code casts each value before adding. If it added two int values first, a sum of two large values could overflow. The next section shows that problem.
The search loop stops when lo passes hi. In a correct run, the loop always returns before that happens, so the final throw only fires when the input is not sorted and the search cannot find a valid cut.

How fast is it?

The loop runs once per halving of the range lo to hi. That range starts with m + 1 values, so the loop runs about log2(m + 1) times. Each pass does a fixed amount of work, so the total time is O(log(min(m, n))). The swap at the top costs one comparison. The function uses a fixed amount of extra memory, because it keeps only a few integers.

Common mistakes

The first mistake is forgetting the swap. If a is the longer list, the value j = leftCount - i can go below 0 or above n. The program then reads outside the list. In this build of g++ 15, the span check stops the program. Running the function with the swap removed, with a set to 1 2 3 4 5 6 7 8 and b set to 9, printed this and stopped with exit code 134.

/usr/include/c++/15/span:302: constexpr std::span<_Type, _Extent>::element_type& std::span<_Type, _Extent>::operator[](size_type) const [with _Type = const int; long unsigned int _Extent = 18446744073709551615; reference = const int&; size_type = long unsigned int]: Assertion '__idx < size()' failed.

Without the span check, the same mistake reads memory that does not belong to the list, and the answer is random. The check is a sign of the bug, so read the line that names the index and go back to the value of j.

The second mistake is getting leftCount wrong. If the code uses total / 2 instead of (total + 1) / 2, the left side does not get the extra middle value when the total is odd. Running that version on 1 3 and 2 printed 1, where the correct answer is 2. It also printed 1 for 1 2 3 and an empty list, where the correct answer is 2. The rule to remember is that the left side gets the extra value.

The third mistake is adding two int values before dividing by 2. With int x = INT_MAX and int y = INT_MAX, the expression (x + y) / 2 overflows. In C++, signed overflow is undefined behaviour, which means the program may do anything. A g++ build with -O0 printed -1, and the correct average is 2147483647. Converting to double before the addition avoids the problem.

The fourth mistake is forgetting <climits>. Without it, the compiler reports this error.

nolimits.cpp: In function ‘int main()’:
nolimits.cpp:5:13: error: ‘INT_MIN’ was not declared in this scope
    5 |     int x = INT_MIN;
      |             ^~~~~~~
nolimits.cpp:4:1: note: ‘INT_MIN’ is defined in header ‘<climits>’; this is probably fixable by adding ‘#include <climits>’
    3 | #include <iostream>
  +++ |+#include <climits>
    4 | int main() {

The fifth mistake is handling the edge cases with the wrong sentinel. If aLeft is set to 0 when i is 0, a list of negative numbers gets a wrong left value. The sentinel must be the smallest possible int, so that it never wins a comparison that it should lose.

Practice

Exercise 1. Find the median of 1 3 5 7 and 2 4 6 8 together. Give the answer as a number.

Show the answer

The eight values sorted are 1 2 3 4 5 6 7 8. The two middle values are 4 and 5, so the median is (4 + 5) / 2 = 4.5. Calling findMedianSortedArrays from this lesson on these two lists returns 4.5.

Exercise 2. One list is empty and the other is 1 2 3 4 5. What is the median? Explain how the search handles the empty list.

Show the answer

The median is 3. The empty list is the shorter one, so no swap happens, and m = 0. The search range for i is only 0. The cut is at i = 0, which means no values come from the empty list. Then j = leftCount is 3, which takes three values from the other list. The left side holds 1 2 3, so the median is max of the left values, which is 3.

Exercise 3. Trace the search for 1 3 and 2 by hand, using the rule from this lesson. Write down the value of i and j at each step, and say which check decides the answer.

Show the answer

The first step uses lo = 0 and hi = 2, so i = 1 and j = 1. The cut is valid, because 1 <= 2 and 2 <= 3. The median is max(1, 2) = 2. The only check that matters is the test that both sides are in order, because the cut is valid on the first step and no move of lo or hi is needed.

Exercise 4. Explain in plain words why the code searches the smaller list rather than the larger one.

Show the answer

The search runs over the number of values taken from the first list, from 0 to m. A smaller m means fewer steps, so the search takes about log2(m + 1) steps. The other reason is that the count taken from the second list, j = leftCount - i, must stay between 0 and n. When the first list is the smaller one, that count stays in range for every step. So the code swaps the lists first, and then searches the smaller one.

Exercise 5. For an odd total, the code returns max(aLeft, bLeft). Explain why it does not return min(aRight, bRight).

Show the answer

The left side has one more value than the right side when the total is odd, because leftCount is (total + 1) / 2. The median is the largest value on the left side, so it is max(aLeft, bLeft). The smallest value on the right side is larger than or equal to the median, so it is not the median in general. For example, with 1 2 3, the left side holds 1 2 and the right side holds 3. The median is 2, and min(aRight, bRight) would give 3.

Summary

The median of two sorted lists is the middle value of the two lists taken together, and it does not need the lists to be merged.
The search chooses how many values from the first list go on the left side, and then fixes the number from the second list.
A cut is valid when every left value is no larger than every right value, which takes two comparisons.
The search runs over the smaller list, which gives O(log(min(m, n))) time, and the code swaps the lists so that the count from the second list stays in range.
Empty sides use the smallest or largest possible int as a sentinel, so comparisons still work at the ends.
Convert to double before adding two values to avoid integer overflow.

Median of two sorted arrays

Why this matters

What the median is

The slow method first

The big idea: cut both lists

Choosing the cuts

Why search the smaller list

Worked example 1: 1 3 and 2

Worked example 2: 1 2 and 3 4

Worked example 3: -5 0 5 10 and -3 8

The C++ code

How fast is it?

Common mistakes

Practice

Summary

Stuck? Ask the tutor

Worked example 1: `1 3` and `2`

Worked example 2: `1 2` and `3 4`

Worked example 3: `-5 0 5 10` and `-3 8`