Median of Two Sorted Arrays

The median of a collection of numbers is its middle value once they are sorted — the point that splits the data into a smaller half and a larger half, or the average of the two middle values when the count is even. Here you are given two arrays that are each already sorted in ascending order, and you return the median of all of their values combined. This is the well-known "Median of Two Sorted Arrays" interview problem (LeetCode 4); the catch is the target running time. See median for background.

Signature

medianOfTwoSorted(a, b)  // a and b each sorted ascending -> number (may be a .5)

Examples

medianOfTwoSorted([1, 3], [2]);       // 2    (combined [1, 2, 3] -> middle value)
medianOfTwoSorted([1, 2], [3, 4]);    // 2.5  (combined [1, 2, 3, 4] -> average of 2 and 3)
medianOfTwoSorted([], [1, 2, 3, 4]);  // 2.5  (one array may be empty)

Notes

• Both sorted — a and b are each in ascending order. You never sort them yourself.
• Never both empty — at least one array holds a value, though either one alone may be empty.
• Even totals average — when the combined length is even, the median is the average of the two middle values, so the result can be a .5 (a non-integer). An odd total returns the single middle value.
• Values vary — numbers may be negative and may repeat across the two arrays.
• Beat the merge — the interview target is O(log(min(m, n))) time, not the O(m + n) you get from merging the two arrays and indexing the middle.