Two library shelves hold books sorted by catalogue number: left and right (both ascending, possibly with repeats across shelves). Without merging the shelves, find the k-th smallest catalogue number overall (1-indexed). Write kth_across(left, right, k) returning it. Aim for a solution that does far less than k work by throwing away a block of books at each recursive step.
Examples
Input: left = [1, 4, 9], right = [2, 3, 10, 12], k = 4
Output: 4
Explanation: merged order is 1, 2, 3, 4, 9, 10, 12; the 4th is 4.
Input: left = [], right = [5, 6], k = 2
Output: 6
Constraints
0 <= len(left), len(right) <= 10**4,1 <= k <= len(left) + len(right)- Target complexity: O(log k) recursive calls; the recursion depth is well under 50.
Goals
- Discard about k/2 elements from one list per call
- Handle the base cases where one list is exhausted or k is 1
- Reason about which half of the discarded elements cannot contain the answer