双向搜索是对于深度优先搜索的一种优化，它的基本思想是：把(dfs)从一端开始改为从两端开始，从而有效减少搜索状态
如果上面的定义不懂的话，请看下面两这张图(设(n)是搜索层数)：
上面这个图就是普通的(dfs)在每次拓展两个节点的情况下所产生的的搜索树的形状
这棵搜索树，每一个节点都代表了一次递归调用，我们很容易可以看出来它的复杂度是(O(2^n))(满二叉树情况下)(其实减不减1无所谓了)
下面这个是双向搜索所产生的两棵搜索树(一颗红色，一颗蓝色)
我们在这两棵搜索树上分别得到了(4)和(2)种结果，现在组合一下(绿色部分)，得到了(4*2=8)种结果，和原来的搜索结果一样
那么分析复杂度：我们一次搜索的复杂度(O(2^frac{n+2}{2}))，两次搜索就是(O(2^{frac{n+4}{2}}))
如果我们朴素的统计答案，那么一次搜索会产生(2^{frac{n}{2}})种结果，两次则平方，变成了(2^n)次统计
把复杂度相加：总复杂度是(O(2^{frac{n+4}{2}}+2^n))
Q：怎么还慢了呢？混蛋！
A：(没错就是慢了)
Q：那你讲个P！(握紧小拳头)
A：(先别打，先别打！我还没讲完呢！)
Part 2：真正的双向搜索复杂度分析上面的方法慢了，主要原因是我们选择了“朴素”的统计答案
考虑怎么优化：我们统计答案的第一步就是判断这个组合得到的最终答案合不合法
那么，我们可以考虑对其中一个答案数组排序，然后以另一个答案数组为查找元素进行二分查找
假设找到一个元素，因为在它之前的元素一定小于它，所以在这个元素之前的元素也都合法，这样我们就不用一个一个的统计答案了，提高了效率
分析这么做的时间复杂度：
(sort())快速排序一遍(O(frac{n}{2}logn))
进行(frac{n}{2})次二分查找，(O(frac{n}{2}logn))
统计答案总复杂度：(O(nlogn))
算法总复杂度：(O(2^{frac{n+4}{2}}+nlogn))
这不就快了吗
Part 3：例题传送门：https://www.luogu.com.cn/problem/P4799
题目中要求我们求出在不超过总预算的情况下，小B去看比赛的方案数
首先，数据范围(nleq 40)，普通的(dfs)肯定会(TLE)的飞起，我们考虑双向搜索
令(Mid=frac{n}{2})，我们第一次从(1)搜索到(Mid)，把答案记录到序列(a)中，第二次从(Mid+1)搜索到(n)答案记录到序列(b)中
现在统计答案，从(a)，(b)中任选一个序列进行快速排序，(这里排哪个应该对时间有影响，但是不大)，这里假设我们对(b)排序
我们的满足答案的状态是：(a_i+b_j