Given two arrays a and b, each already sorted ascending, return the median of all their values combined. With an odd total count the median is the middle value; with an even total count it is the average of the two middle values.
- Either array may be empty (but not both)
- Merging is
O(m + n); the target here is O(log(min(m, n))) - Binary search a partition point in the shorter array: cut both arrays so the left halves together hold exactly half the elements and every left value is at most every right value
- Use
-Infinity and Infinity for the missing neighbours when a cut lands at an array's edge