二分简介

二分查找是一种可以快速在单调数组中查询某元素出翔位置的方法。普通二分的实现方式是设定查找左边界和右边界，通过将元素出现范围划分成两半，判断元素在那一半里面来缩小元素出现范围。

二分答案是一种快速查找单调函数的因变量为某值时函数的自变量的方法。在某些算法竞赛题目中，使用二分答案时要精心设计划分方式（让中间往左偏或往右偏，mid = (l + r) / 2 或 mid = (l + r + 1) / 2）以避免死循环。不恰当的设计方式通常会让二分答案卡在答案范围为 $2$ 的情况。

如果出现了这种情况，可以尝试另一种二分方式。但是二分的模板有很多，一个一个地试太浪费时间了，怎么写出一遍过的二分？

另一种二分

这种二分和上面的思想是同一样的，但是不同点在于实现方式并不是确定范围，而是通过从起点开始以不同的步长跳到答案（类倍增思想）。具体实现方式：

将指针设为查找范围的左边界，步长设为查找范围的长度；

一直执行直到 步长为0：
	如果 指针加上步长没有超过查找右界 而且 答案不在指针加上步长左边：
		指针加上步长；
	否则：
		步长除以二，不保留余数；

这种二分方式和普通二分时间复杂度是一样的，但是绝对不会卡住。

时间复杂度证明

不难看出，步长最多除 ${\log }_2(n)$ 次（$n$ 为查找范围长度），如果步长为 $k$：

• 如果步长为 $k$ 要跳三次，那么在讨论步长为 $k\cdot 2$ 或 $k\cdot 2+1$ 的时候就可以跳，不符合条件，所以步长为 $k$ 最多跳两次。

所以每一种步长跳两次，最多 $2{\log }_2(n)$，常数大了一点。当 $n$ 可以通过 $2$ 的 $k$ 次幂减 $1$ 时可以卡到算法常数极限（如 $32767$）。

Sample Code

以下为洛谷 P2249 的 AC 代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, a[1000100];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	while (m--) {
		int x;
		cin >> x;
		int p = n, idx = 0;
		while (p) {
			if (idx + p <= n && a[idx + p] < x) {
				idx += p;
			}
			else {
				p >>= 1;
			}
		}
		idx++;
		if (a[idx] == x) {
			cout << idx;
		}
		else {
			cout << -1;
		}
		cout << ' ';
	}
	return 0;
}

由于取最左边，所以我们可以找到小于我们要查找的数的最大值，如果它右边就是我们要查找的数，就可以找到。