折半搜索
1.前言
在计算机科学中，折半搜索，通常称之为 meet-in-the-middle，也称为二分搜索、对数搜索，是一种在有序数组中查找某一特定元素的搜索算法。其做法为将整个搜索的过程分为两部分，然后每部分分别进行搜索，最后将得到两个答案序列，再将答案序列进行合并，即可得到最终的答案。
折半搜索是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数 a_0\sim a_4，要查找的数是 x，其基本思想是：设查找数据的范围下限为 l=0，上限为 r=4，求中点 mid=(l+r)/2，用 x 与中点元素 a_{mid} 比较，若 x 等于 a_{mid}，即找到，停止查找；否则，若 x 大于 a_{mid}，替换下限 l=mid+1，到下半段继续查找；若 x 小于 a_{mid}，换上限 r=mid-1，到上半段继续查找；如此重复前面的过程直到找到或者 l>r 为止。如果 l>r，说明没有此数，输出找不到信息，程序结束。
该方法是查找的范围不断缩小一半，所以查找效率较高。
折半搜索的优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
我们知道，搜索的时间复杂度往往是指数级别的。
比如，在每一层搜索时，假如都有两种选择，那么其时间复杂度为 \mathcal{O}\left(2^n\right)。当 \large n 较大时，往往会导致超时。此时，如果使用折半搜索，其时间复杂度将缩小为 \mathcal{O}\left(2^{\frac{n}{2}}+\text{合并操作的时间复杂度}\right)。
2.算法讲解
例题1
P4799 [CEOI2015 Day2]世界冰球锦标赛
题意描述
Bobek 有 m 元钱，总共有 n 场比赛，每场比赛的门票价格为 \large a_i。
问 Bobek 有多少种买票方案。
限制条件：1\le n\le40，1\le m\le10^{18}，\large a_i\le10^{16}
且：若方案 1 中观看了某场比赛，方案 2 中未观看该场，则认为两种方案不同。
因为 m 最大为 10^{18}，背包就不行了，但是 n 最大为 40，于是答案的最大值就是 2^{40}，普通的搜索会爆，但是折半搜索只用 2 次 2^{20} 就可以计算出所有的答案了（2^{20}=1,048,576）。
我们可以将所有比赛分成两部分，对这两部分分别进行搜索，然后使用 vector 来储存搜索过程中产生的可能的花费。最后再将两部分进行合并，得出最终的答案。
代码步骤：
$2.$ 然后将一个数组进行排序，让他成为有序数组（最好是升序，因为这样可以使用万能的 $STL:upper\_bound$）
$3.$ 最后枚举另一个数组里的所有值，然后计算 $m-val\_b_i$ 在 $a$ 数组中的位置，因为如果其在 $x$ 的位置（或者不在但是第一个 $\le m-val\_b_i$ 的数的位置在 $x$），那么 $1\sim x$与 $val\_b_i$ 搭配的方案都是可以的。
### 参考代码
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MaxN=3e6+5;
int n,cnt_front,cnt_back;
long long m,ans,a[MaxN],val_front[MaxN],val_back[MaxN];
void dfs_front(int l,int r,long long sum){
if(sum>m){
return ;
}
if(l>r){
val_front[++cnt_front]=sum;
return ;
}
dfs_front(l+1,r,sum);
dfs_front(l+1,r,sum+a[l]);
}
void dfs_back(int l,int r,long long sum){
if(sum>m){
return ;
}
if(l>r){
val_back[++cnt_back]=sum;
return ;
}
dfs_back(l+1,r,sum);
dfs_back(l+1,r,sum+a[l]);
}
int main(){
scanf("%d%lld",&n,&m);
for(register int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
dfs_front(1,n/2,0);
dfs_back(n/2+1,n,0);
sort(val_front+1,val_front+cnt_front+1);
for(register int i=1;i<=cnt_back;i++){
ans+=upper_bound(val_front+1,val_front+cnt_front+1,m-val_back[i])-val_front-1;
}
printf("%lld",ans);
return 0;
}
```
最终的时间复杂度为 $\LARGE\mathcal{O}\left(2^{\frac{n}{2}+1}+\frac{n+\log^{\frac{n}{2}}_2}{2}\right)$。前者为分别搜索的时间复杂度，后者为合并的时间复杂度。
做完这题我们发现，折半搜索适用于当 $n\le45$ 的搜索题。所以当 $n=20\sim45$ 时，我们可以用折半搜索来写。
## 感谢[myee](https://www.luogu.com.cn/user/105050)提供的折半搜索题单[折半搜索题单](https://www.luogu.com.cn/training/104024#information)