目录
一、整数二分
二分查找分为整数二分和浮点数二分，一般所说的二分查找都是指整数二分。
1.1 整数二分查找模板
满足单调性的数组一定可以使用二分查找，但可以使用二分查找的数组不一定需要满足单调性。
不妨假设我们找到了条件 \(C_1\)，它和它的 对立条件 \(C_2\) 能够将数组 \(a\) 一分为二，如下图所示：
因为 \(C_1\) 和 \(C_2\) 互为对立，故总有 \(C_1\cup C_2\equiv \text{True}\)，\(C_1\cap C_2\equiv \text{False}\)（用C++语言描述，就是 c1 || !c1 总是为真，c1 && !c1 总是为假）。换句话说，\(\forall \,x\in a\)，\(x\) 至少 满足 \(C_1\) 和 \(C_2\) 中的一个，且 \(x\) 不会同时满足 \(C_1\) 和 \(C_2\)。
观察上图可以发现，索引3和索引4这两个位置都可以作为\(C_1\)和\(C_2\)的分界点。其中，索引3是红色区域的右边界，索引4是绿色区域的左边界。而我们接下来要讨论的二分查找模板就是用来 寻找\(C_1\)和\(C_2\)的分界点的。
1.1.1 寻找右边界的二分查找
前面说过，\(C_1\)和\(C_2\)的分界点 一共有两个 ，因此我们的整数二分查找模板也有两个。一个用来查找右边界（即左侧的分界点，对应索引3），一个用来查找左边界（即右侧的分界点，对应索引3）。这里首先介绍查找右边界的模板。
因为查找的是 红色区域的右边界 ，所以先定义一个函数 check(i)，其中参数i是索引。当i位于红色区域，即 \(0\leq i \leq 3\) 时，check(i) 为真；当i位于绿色区域，即\(4\leq i \leq 7\)时，check(i) 为假。
初始时设置左右两个指针分别位于数组的左右两端，每次循环时计算 \(mid=\frac{l+r}{2}\)（至于mid到底取多少稍后会说），然后判断 check(mid) 的值（为实现二分查找， 我们需要确保每次缩小区间时答案都落在区间内 。这样一来，当最终 l == r 时，l 就是我们需要的答案）。如果 check(mid) 为真，说明mid位于红色区域，且mid有可能就是右边界 ，因此接下来令l=mid来缩小查找范围（因为我们要保证缩小后的区间仍然包含答案）；如果 check(mid) 为假，说明mid位于绿色区域，且mid必不可能是红色区域的右边界 ，因为mid最多是索引4，因此令r=mid-1来缩小查找范围。
接下来重点关注mid到底该取多少。如果\(mid=\frac{l+r}{2}\)，其中的除法代表整除，在某一轮循环出现了r-l=1，则\(mid=\frac{2l+1}{2}=l\)。若 check(mid) 为真，则更新后的区间仍然为\([l,r]\)，这就会导致无限循环。事实上，只需要取\(mid=\frac{l+r+1}{2}\)，若 check(mid) 为真，则mid=r，更新后的区间为\([r,r]\)，循环结束。若 check(mid) 为假，则更新后的区间为\([l,l]\)，循环结束。
寻找右边界的二分查找模板：
int right_bound(int l, int r) {
while (l < r) {
int mid = (l+r+1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
1.1.2 寻找左边界的二分查找
类似1.1.1节中的分析，因为查找的是 绿色区域的左边界 ，所以先定义一个函数 check(i)，其中参数i是索引。当i位于绿色区域，即 \(4\leq i \leq 7\) 时，check(i) 为真；当i位于红色区域，即 \(0\leq i \leq 3\) 时，check(i) 为假。
初始时设置左右两个指针分别位于数组的左右两端，每次循环时计算 \(mid=\frac{l+r}{2}\) （至于mid到底取多少稍后会说），然后判断 check(mid) 的值。如果 check(mid) 为真，说明mid位于绿色区域，且mid有可能就是左边界 ，因此接下来令r=mid来缩小查找范围；如果 check(mid) 为假，说明mid位于红色区域，且mid必不可能是绿色区域的左边界，因为mid最多是索引3，因此令l=mid+1来缩小查找范围。
接下来重点关注mid到底该取多少。如果 \(mid=\frac{l+r}{2}\)，其中的除法代表整除，在某一轮循环出现了r-l=1，则 \(mid=\frac{2l+1}{2}=l\)。若 check(mid) 为真，则更新后的区间为\([l,l]\)，循环结束。若 check(mid) 为假，则更新后的区间为\([r,r]\)，循环结束。综上所述，mid取 \(\frac{l+r}{2}\) 即可。
寻找左边界的二分查找模板：
int left_bound(int l, int r) {
while (l < r) {
int mid = (l + r) >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
二、浮点数二分
2.1 浮点数二分查找模板
相比整数二分，浮点数二分就要简单许多了，因为浮点数二分不涉及到边界问题。
浮点数二分 通常用来求某个数 \(x\) 的近似值（ \(x\) 不易直接求得，例如 \(x=\sqrt{2}\) 等）。由于此时左右两个指针也均为浮点数，所以我们不能直接判断 l == r，而是判断 r - l 是否小于预先设定的精度。
模板如下：
double fsearch(double l, double r, double eps) {
while(r - l > eps) {
double mid = (l+r) / 2;
if(check(mid)) r = mid;
else l = mid;
}
return l;
}
一些注意事项：
- 若要求精确到小数点后
k位，则eps取 \(10^{-(k+2)}\) - 若 \(mid\geq x\)，则
check(mid)为真，否则为假
三、使用STL进行二分查找
3.1 std::binary_search
template< class ForwardIt, class T >
bool binary_search( ForwardIt first, ForwardIt last, const T& value );
该函数用来检查 [first, last) 区间内（该区间已排序）是否有数字 等于 value，如果有返回 true，否则返回 false。
3.2 std::lower_bound
template< class ForwardIt, class T >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value );
该函数用来返回 [first, last) 区间内（该区间已排序） 首个大于等于 value 的元素的迭代器，如果找不到这种元素则返回 last。
3.3 std::upper_bound
template< class ForwardIt, class T >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value );
该函数用来返回 [first, last) 区间内（该区间已排序） 首个大于 value 的元素的迭代器，如果找不到这种元素则返回 last。
3.4 std::equal_range
template< class ForwardIt, class T >
std::pair<ForwardIt, ForwardIt>
equal_range( ForwardIt first, ForwardIt last, const T& value );
该函数用来返回 [first, last) 区间内（该区间已排序） 所有等于 value 的元素的「范围」。「范围」实际上是由两个迭代器构成的 pair。pair 中的第一个元素是 std::lower_bound 的返回值，pair 中的第二个元素是 std::upper_bound 的返回值。