如何在两个排序数组的并集中找到第k个最小元素？

您已掌握，继续前进！并注意索引…

为了简化一点，我假设N和M> k，所以这里的复杂度为O（log k），即O（log N + log M）。

伪代码：

i = k/2j = k - istep = k/4while step > 0    if a[i-1] > b[j-1]        i -= step        j += step    else        i += step        j -= step    step /= 2if a[i-1] > b[j-1]    return a[i-1]else    return b[j-1]

为了演示，您可以使用循环不变i + j = k，但我不会做所有作业：)