保持二分的比较结果

思路

先在原排列上完整模拟题目指定的二分过程，记最终下标为 $L$，数字 $x$ 的原位置为 $pos$。如果两者相同，原排列已经满足要求。否则，将 $p_L$ 与 $p_{pos}$ 交换即可。

关键是交换以后，二分仍然走原来的路径。这样最终下标仍为 $L$，但该位置的值已经变成 $x$。

做法

读取排列时找到 $x$ 的位置。按照题面使用 $l=1,r=n+1$，在 $p_m\le x$ 时更新左端点，模拟直到左右端点相邻。

若最后 $l=pos$，输出零次操作；否则输出一次操作，交换 $l$ 与 $pos$。题目允许至多两次，但并不要求一定使用两次。

正确性证明

若 $L>1$，则 $L$ 一定是某次比较后更新得到的左端点，所以交换前 $p_L\le x$。另一个交换位置原来存放的就是 $x$。交换后，这两个位置对条件“当前位置的值不超过 $x$”的判断均未改变，其他位置也没有变化。因此二分每一步选择同一个分支，最后仍停在 $L$。

若 $L=1$ 且 $p_1\le x$，同样可用上述比较值不变的论证。

最后考虑 $L=1$ 且 $p_1>x$。在循环中，中点总大于当前左端点，所以位置 $1$ 从未作为中点被读取；位置 $pos$ 也不可能被读取，否则由于其值为 $x$，左端点会被更新到至少 $2$，与 $L=1$ 矛盾。因此交换的两个位置均不在原二分读取路径上，所有已读取值不变，路径仍然不变。

综上，交换后二分仍停在 $L$，且 $p_L=x$。如果原来已经满足要求，则零次操作显然合法。算法最多使用一次交换，符合题目的限制。

复杂度

读取排列并找到 $x$ 使用 $O(n)$ 时间，模拟二分使用 $O(\log n)$ 时间，总时间为 $O(n)$。存储排列需要 $O(n)$ 空间。

部分分思路

极小规模可以枚举最终排列，检查二分结果，并通过置换的循环分解判断能否在两次交换内从原排列得到它。依次把每个位置换成目标值，就能构造最少交换序列。这个方法需要阶乘数量的枚举。

中等规模可以先试零次交换，再枚举每一对位置，交换后实际运行二分。上述定理保证一定存在至多一次交换的解，所以这一枚举完整正确，时间复杂度为 $O(n^2\log n)$。

当 $x=1$ 时，把 $1$ 放到首位后，其余中点上的值都大于 $x$，二分停在首位；当 $x=n$ 时，所有比较都向右走，最终停在末位，只需把 $n$ 放到末位。这两个端点情形都可以直接把 $x$ 放到下标 $x$，不必分析任意排列的二分路径。