本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-07-20 21:15:02

原理

假设有 $n$ 个节点，而为了搜一个解需要遍历这 $n$ 个点。

如果复杂度较低，如遍历的复杂度为 $O(n)$，倒没有必要用这个算法。

但是如果复杂度很高，如 $O(n^2)$，而 $n \le 20000$；或者 $O(2^n)$，$n \le 40$ 等，就很有用了。

这个算法是分别从两端开始搜，两端分别搜索 $\frac{n}{2}$ 个节点，最后再把两端搜索到的结果拼接起来。

原来的 $O(n^2)$ 复杂度虽然还是 $O(n^2)$，但是由于 $n$ 除了 $2$，效率提升很大。

而 $O(2^n) \rightarrow O(2^\frac{n}{2})$，效率提升巨大。