789. The Median of Two Sorted Lists

Two non-decreasing lists are given, of lengths m and n. Print the median of the m + n values taken together.

When m + n is odd the median is the middle value. When it is even it is the average of the two middle values, so the answer is either a whole number or a whole number plus a half. Print it with EXACTLY one digit after the decimal point.

1 3 and 2 -> 2.0 merged 1 2 3 1 2 and 3 4 -> 2.5 merged 1 2 3 4 1 1 1 and 1 1 1 -> 1.0 -9 -7 -5 and -4 -2 -> -5.0 merged -9 -7 -5 -4 -2

## This is the sequel to problem 628

Problem 628 asks for the kth smallest across two sorted lists and answers it with an O(k) merge walk, one step per value. That is the right tool when k is small. Here k is the middle of the data, so the walk is O(m + n) and the whole point is to beat it. 628's statement says outright that the logarithmic method is left open; this is it.

## Stop merging. Start cutting.

Do not look for the median. Look for the CUT.

Take the first i values of list A and the first j values of list B, with i + j = (m + n + 1) / 2, integer division. That is one variable, not two, because j is forced by i. The cut is correct when nothing on the left is bigger than anything on the right:

A[i-1] <= B[j] and B[j-1] <= A[i]

When both hold, the left side holds exactly the smallest (m + n + 1) / 2 values and

left = max(A[i-1], B[j-1]) right = min(A[i], B[j])

give the median: left when the total is odd, the average of left and right when it is even. Choosing (m + n + 1) / 2 rather than (m + n) / 2 is what makes the odd case fall out as left with no separate branch.

## Why one comparison is enough, and why it is monotone

As i grows by one, A[i-1] grows and j shrinks so B[j-1] shrinks. So the test A[i] < B[j-1], meaning "still too few taken from A", is true for a run of small i and false afterwards. It flips once and never flips back, which is exactly what a binary search needs.

Search for the first i where it is false. The other condition, A[i-1] <= B[j], is then automatic, so only one of the two needs testing inside the loop.

## Search the SHORTER list

Swap the lists if necessary so that m <= n. Two reasons: the cost becomes O(log(min(m, n))), and more importantly j = (m + n + 1) / 2 - i is then guaranteed to land inside 0 .. n for every i in 0 .. m. Without the swap j can go negative and the indexing is meaningless.

## The missing neighbours

When i is 0 there is no A[i-1], and when i is m there is no A[i]. Treat the absent left neighbour as minus infinity and the absent right neighbour as plus infinity, so those cuts compare correctly instead of needing four special cases. Use a sentinel comfortably outside the value range; 10^18 and its negative are plenty.

The inputs 100 against 1 2 3 4 5 and 1 2 3 4 5 against 100 are the two that exercise this, one on each side, and they are both in the tests.

## Printing the half

The answer doubled is always a whole number, so form s = left + right for an even total and s = 2 * left for an odd one, then print s / 2 followed by .0 or .5 according to whether s is odd.

Negatives are where this gets fiddly, and not in the way it first looks. In C, C++ and Java the divide truncates towards zero, so s = -5 gives s / 2 = -2, and pasting .5 onto -2 happens to print -2.5, which is correct. The case that breaks is s = -1: the median is -0.5, the quotient is 0, and 0 carries no sign, so the minus disappears and the answer prints as 0.5. Python is worse rather than better here, because // floors instead of truncating and -5 // 2 is -3, which prints -3.5. Split the sign off first, format the magnitude, then re-attach the minus, and all three behave the same.

A floating-point divide is not actually wrong at these bounds, and the honest version of that warning is worth more than the usual one. |s| never exceeds 2000000000, far below the 9007199254740992 at which a double stops representing every integer exactly, so s / 2.0 is exact and a %.1f print is correct on every legal input. The integer route is still the one to learn: it stays exact as the bounds grow, and it removes the rounding question instead of answering it for one particular set of constraints.

## Overflow

Every number this problem computes is comfortably inside 32 bits. left and right are input values, so |s| never passes 2000000000 against a ceiling of 2147483647, and m + n stops at 2 * 10^5.

The SENTINELS are what force a wider type. An absent neighbour has to lose every comparison on one side and win every comparison on the other, and 10^18 is picked for that margin, not because anything computed here is that large. Held in 32 bits it would not be a sentinel at all. Pick the sentinel and the type together.

## Cost

Time O(log(min(m, n))). Space O(1) beyond the input.

Constraints - `1 ≤ m, n ≤ 100000` - `-10^9 ≤ each value ≤ 10^9` - both lists are non-decreasing