I have 2 sorted arrays of integers, how do I find the kth biggest item in O(logn) time? [duplicate]

Question

I was asked this question in an interview. I was able to do it in O(n) time obviously, but I fail to think about a way to solve in in O(logn). It sounds like using some divide-and-conquer algorithms but I'm not sure.

Answer 1

Truncate both to size k. If necessary, have the program imagine enough infinities at the end of one or both arrays to bring them up to size k; this will not affect the asymptotic runtime. (In a real implementation, we would probably do something more efficient.)

Then, compare the k/2'th elements of each array. If the elements compared equal, we've found the k'th element; otherwise, let the array with the lower k/2'th element be A and the other be B. Throw away the bottom half of A and the top half of B, then recursively find the k/2'th element of what remains. Stop when we hit k=1.

On every step, the bottom half of A is guaranteed to be too small, and the top half of B is guaranteed to be too big. The k/2'th element of what remains is guaranteed to be bigger than the bottom half of A, so it's guaranteed to be the k'th element of the original.

Proof of concept, in Python:

def kth(array1, array2, k):
    # Basic proof of concept. This doesn't handle a bunch of edge cases
    # that a real implementation should handle.
    # Limitations:
    #   Requires numpy arrays for efficient slicing.
    #   Requires k to be a power of 2
    #   Requires array1 and array2 to be of length exactly k
    if k == 1:
        return min(array1[0], array2[0])
    mid = k//2 - 1
    if array1[mid] > array2[mid]:
        array1, array2 = array2, array1
    return kth(array1[k//2:], array2[:k//2], k//2)

I have tested this, but not much.