折半搜索（meet in middle）-526互联

折半搜索

做法为将整个搜索的过程分为两部分，然后每部分分别进行搜索，最后将得到两个答案序列，再将答案序列进行合并，即可得到最终的答案。

可以发现，当状态非常之多的时候，这种优化还是非常明显的，最优情况下可以直接把复杂度开个根号。

需要注意的是，折半搜索应用的时候需要满足以下条件：

搜索各项不能相互干扰。
需要满足搜索状态可逆，就是说一个状态可以从两个方向都得到。

折半搜索其实还是用的比较广泛的。

BFS ,DFS 还有状压 DP 都有类似的应用。

折半搜索一般的难点就在于最后的答案序列合并。（可能会使用一些奇奇怪怪的高深的玩意才能搞得出来）

实现非常灵活，需要按照题目来进行选择。

一般比较常见的排序后二分，双指针还有哈希表。

逐个分析一下：

1.排序后二分

复杂度肯定是带为什么正确？

在一个有序的序列中，如果我们可以找到一个位置可以做到对答案有贡献，那么这个位置之前的所有位置都是可以对答案有贡献的,所以直接统计就好。

1 sort(a+1,a+1+cnta);
2 for(re int i=1;i<=cntb;i++)
3     ans+=upper_bound(a+1,a+1+cnta,m-b[i])-a-1;

2.双指针

一般是线性的，效果很不错，代码比较好写。

缺点就是比较难想，需要考虑一些问题（例如单调性）。

1 int l=cnta,r=1;
2 for(r=1;r<=cntb;r++){
3     while(a[l]+b[r]>m)l--;//m是一个限制条件
4     if(a[l]&&b[r])ans+=(l-1);  
5 }

3.哈希表

也是线性，至于具体如何就要看脸了。

如果不被卡的话哈希表确实是一种非常不错的选择。

具体就是先处理一半，然后把搜到的答案存到哈希表里，然后搜另一半，之后再去哈希表里找，把结果合并就可以了。

 1 void dfs1(){//搜索一半 
 2     if (到达边界){
 3         add(hash(x)); 
 4         return;
 5     } 
 6     ... 
 7 }
 8 
 9 void dfs2(){//处理另一半 
10     if (到达边界){
11         ans+=sum[hash(x)];
12         return;
13     } 
14     ... 
15 }