序列二分¶
引入¶
问题
现在有 \(n\) 个数，第 \(i\) 个数为 \(a_i\)。紧接着有 \(m\) 个询问，每一个询问给出了一个整数 \(x\)，要你判断 \(x\) 是否在 \(a\) 当中出现过。
普通算法¶
对于每一个询问，我们直接遍历 \(n\) 个数，如果遇到了任何一个正好等于 \(x\) 的数，那么就说明序列 \(a\) 当中有 \(x\)，我们就可以直接退出循环。但是在最坏情况下，我们可能每一次都需要遍历到最后一个数，而询问有 \(m\) 次，那么时间复杂度就是 \(\mathcal O(nm)\)。在 \(n\) 或 \(m\) 过大的时候可能会超时，因此我们需要选择一种更好的算法。
可以尝试使用一个桶来记录所有出现过的数，也就是将每一个 \(a_i\) 都存到下标里面，这样子就可以 \(\mathcal O(1)\) 处理单个询问了。但是我们的数没说不能为负数，而且这些数可能会很大，开一个桶很有可能会爆空间。
接下来，就是我们的二分算法了。
二分算法¶
我们可以直接对 \(a_i\) 排序，使得 \(a_i\le a_{i+1}\)。对于每一个询问，最开始答案肯定在 \([l=1,r=n]\) 里面，我们就折中试一试，用 \(a_{(\cfrac{l+r}{2})}\) 与 \(x\) 作比较。如果运气好——这个数正好就等于 \(x\)，那么我们就直接找到了答案；否则，如果这个数大于 \(x\)，就说明答案肯定在前面的区间，那么区间就变成了 \([l,r=\cfrac{l+r}{2}-1]\)；如果这个数小于 \(x\)，就说明答案肯定在后面的区间内，那么区间就变成了 \([l=\cfrac{l+r}{2}+1,r]\)。
重复执行这个操作，知道找到了 \(x\) 所在的地方。如果找不到，那么就说明 \(x\) 不在 \(a\) 里面。
这种每一次都把答案的范围折一半的算法就叫做二分算法，也称作为“中分”。由于每一次都将区间砍成了两半，那么最坏复杂度就取决于 \(n\) 能够除以多少次 \(2\)。很显然，这个数就等于 \(\lfloor\log_2 n\rfloor\)，因此该算法的时间复杂度就为 \(\mathcal O(m\log_2 n)\)。
代码
// 需要对 a 排序
bool check(int x) {
for (int l = 1, r = n; l <= r; ) {
int m = (l + r) >> 1;
if (a[m] == x) {
return 1;
} else if (a[m] > x) {
r = m - 1;
} else {
l = m + 1;
}
}
return 0;
}