Locate the Middle Value Across Two Sorted Inputs
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
Overview: Find the median of two already-sorted integer arrays in logarithmic time, including when one array is empty and the result is fractional.
Constraints
- m == first.length, n == second.length
- 0 <= m <= 1000 and 0 <= n <= 1000
- 1 <= m + n <= 2000 (the two arrays are never both empty)
- -10^6 <= first[i], second[j] <= 10^6
- first and second are each sorted in nondecreasing order
- The algorithm must run in O(log(m + n)) time; a linear merge does not qualify
Examples
Input: ([2, 8], [4])
Expected Output: 4.0
Input: ([1, 5], [2, 8])
Expected Output: 3.5
Hints
- You never need the merged array, only the boundary between its smaller half and its larger half. Taking i values from one array fixes how many values must come from the other.
- Search over the shorter array. A choice of cuts is right exactly when the largest value left of each cut is no greater than the smallest value right of the other cut.
- Treat a cut at the very start or end of an array as having negative or positive infinity on its empty side, so empty arrays and lopsided splits need no special case.