归并第 k 小

为 22 年初赛填的坑。下文统一采用 0-index。

对于两个有序数列 $a,b$，我们可以在 $O(\log n)$ 的时间和 $O(1)$ 的额外空间内找到他们中的第 $k$ 小数，并且常数较小。

考虑二分。维护四个指针 $l1,r1,l2,r2$ 分别表示第 $k$ 小值分别可能出现在两个序列中的哪段区间。

每次令 $m1\gets \lfloor \frac{l1 + r1}{2} \rfloor, m2\gets \lfloor \frac{l2 + r2}{2} \rfloor$：

• 如果 $a_{m1} \le b_{m2}$：

  • 如果 $m1 + m2 < k$，则说明若第 $k$ 小数位于 $a$ 中，则其必须位于 $m1$ 及其右侧，令 $l1 \gets m1 +1$。
  • 否则，说明若第 $k$ 小数位于 $b$ 中，则其必须位于 $m2$ （严格）左侧，令 $r2 \gets m2 - 1$。
• 对于 $a_{m1} > b_{m2}$ 的情形，是对称的。

当出现 $l1>r1$ 或者 $l2>r2$，则表明我们找到了答案。具体地：

• 对于 $l1>r1$：

  • 若 $l1=0$，则说明答案一定在 $b$ 中，返回 $b_{k-1}$。
  • 否则，答案可能为 $a_{l1-1}$，也可能为 $b_{k-l1-1}$，返回他们中较大的一个。
• 对于另一种情况，是对称的。

综上，我们在 $O(\log n)$ 的时间和 $O(1)$ 的额外空间内解决了这个问题。

后来才知道，3 个序列也是可以类似做的，详见元旦激光炮。