AcWing 113. 特殊排序

题目链接：113. 特殊排序 - AcWing题库

根据数学归纳法，假设前 $k - 1$ 个元素已经按要求排成一行，如果能确定第 $k$ 个元素应该放在哪一个前面，即可解决此问题。

我们可以通过这样一种二分法确定第 $k$ 个元素的位置：

若第 $k$ 个元素比第 $mid$ 个元素小，令 $r = mid$，否则令 $l = mid + 1$。

二分的初始区间可设为 $[1, k]$，区间中的 $k$ 这个值表示放在所有 $k - 1$ 个元素之后。

可以证明二分一定可以找到一个合法的位置插入，证明如下。

1. 如果第 $k$ 个元素比第 $mid$ 个元素小。
   继续比较 $k$ 与 $mid - 1$ 这两个元素，若第 $k$ 个元素比第 $mid - 1$ 个元素大，则 $k$ 可以插在 $mid - 1$ 与 $mid$ 之间；
   否则说明元素 $k$ 比元素 $mid$ 小，那就再比较 $k$ 与 $mid - 1$ 这两个元素，依此类推，直到发现第 $k$ 个元素比第 $1$ 个元素小，那就放在最前边。

2. 如果第 $k$ 个元素比第 $mid$ 个元素大，同理。

以上只是一个证明，我们当然不会真的依次比较 $k$ 与每个元素。

实际上通过二分，我们每询问一次（$k$ 与 $mid$），就可以把区间 $[l, r]$ 缩小一半，因此至多 $\log k$ 次询问就可以确定 $k$ 应该放在哪里。

把 $N$ 个元素排成一行的总询问次数不超过 $N \log N$。