Given two sorted arrays, A of length N where N in [0, inf), and B of length M in [0, inf), find the kth smallest element in the union U = A u B in sub O(k) time.
Most of the solutions that I have googled do not consider the case where N and M can be as small as 0, but this solution does.
The strategy to this problem is to chop off part of the arrays that we know can't be the kth element. In doing so, when we recurse on the smaller arrays, the number 'k' will change to reflect tossing out elements smaller than the kth element. The base case is when either one of the arrays is empty, the kth smallest element is the the non-empty array at index k-1:
def kth_smallest(k, a, b)
return b[k-1] if a.empty?
return a[k-1] if b.empty?