java我有两个排序的整数数组，如何在O（logn）时间内找到第k个最大的项？

Question

我在一次采访中被问到这个问题。显然，我能够在O（n）时间内完成，但我没有想到一种在O（logn）时间内求解的方法。这听起来像是在使用一些分而治之的算法，但我不确定

Answer 1

将两个数组的大小都截断为k。如有必要，让程序在一个或两个数组的末尾想象足够多的无穷大，使其达到k的大小；这不会影响渐近运行时。（在实际实现中，我们可能会做一些更高效的事情。）

然后，比较每个数组的第k/2个元素。如果元素相等，我们就找到了第k个元素；否则，让下k/2元素的数组是A，另一个是B。扔掉A的下半部分和B的上半部分，然后递归地找到剩余元素的k/2元素。当我们达到k=1时停止

在每一步中，A的下半部分保证过小，B的上半部分保证过大。剩下的k/2元素保证大于A的下半部分，所以它保证是原始元素的k元素

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)

我已经测试过了，但不多