这是一个作业问题。他们说这需要O(logN + logM)在哪里N，M是数组的长度。
O(logN + logM)
N
M
让我们命名的数组a和b。显然，我们可以忽略所有a[i]和b[i]其中i>ķ。 首先，我们比较a[k/2]和b[k/2]。让b[k/2]> a[k/2]。因此，我们也可以舍弃所有b[i]，其中i> k / 2。
a
b
a[i]
b[i]
a[k/2]
b[k/2]
现在我们有了all a[i]，其中i <k和all b[i]，其中i <k / 2来找到答案。
你下一步怎么做？
您已掌握，继续前进！并注意索引…
为了简化一点，我假设N和M> k，所以这里的复杂度为O（log k），即O（log N + log M）。
伪代码：
i = k/2 j = k - i step = k/4 while step > 0 if a[i-1] > b[j-1] i -= step j += step else i += step j -= step step /= 2 if a[i-1] > b[j-1] return a[i-1] else return b[j-1]
为了演示，您可以使用循环不变i + j = k，但我不会做所有作业：)
