提要
使用二分的条件：具有单调性
注意：二分的思想看似简单，但其实很容易出错
整数二分模板
以单调递增序列的二分为例
给出两个模板：
在单调递增序列中找到x或x的后继(大于x的第一个数)，也就是大于等于x的第一个数的位置
在单调递增序列中找到x或x的前驱(小于x的第一个数)，也就是小于等于x的第一个数的位置
// 找到x或x的后继
int bin_search(int *a, int n, int x) // a 的编码为 [0, n), 左开右闭区间，下面同理
{
int left = 0, right = n - 1;
while (left < right)
{
int mid = left + (right - left) / 2; // 取左中位值
if (a[mid] >= x) right = mid;
else left = mid + 1; // 防止死循环
} // 循环结束时 l = r
return left;
}
// 找到x或x的前驱
int bin_search(int *a, int n, int x)
{
int left = 0, right = n - 1;
while (left < right)
{
int mid = left + (right - left + 1) / 2; // 取右中位数
if (a[mid] <= x) left = mid;
else right = mid - 1;
}
return left;
}
对left, right 的处理
值得注意，第一个模板中循环的结尾left = mid + 1，其原因是整数二分存在取整的问题
例如当 left 等于 2, right 等于 3 时 mid 等于 2，若取 left = mid ，一次循环结束 left 和 right 的值都没有变，程序陷入死循环，解决方法是像模板一样 left = mid + 1
对mid的处理
整数二分的关键是对中间值mid的处理
以第一个模板为例，mid取值有以下几种方法
| 实现方法 | 使用条件 | 可能出现的问题 |
|---|---|---|
| mid = (left + right) / 2 | left >= 0, right >= 0, left + right 未溢出 |
(1)负数情况下会出现向0取整问题 (2)left + right 可能溢出 |
| mid = left + right >> 1 | left + right 未溢出 | left + right 可能溢出 |
| mid = left + (right – left) >> 1 | left – right 未溢出 | left 和 right 一正一负时 right – left 可能溢出 |
值得注意的是，上表中第一个实现方式中向0取整问题是指当 left + right 大于 0 使取的是左中位数，而当 left + right 小于 0 时取的是右中位数，正负区间没有统一取左中位数或右中位数，而后两种方法就没有这个问题，当然在对数组进行二分时，三种实现方法都是可行的
如果是对数组进行二分，因为其下标都大于等于0，个人觉得用上表中的第三个更好
单调递减序列二分
了解上面这些之后，我们也能写出单调递减序列的二分模板
// 找到最后一个大于等于x的数的位置
int bin_search(int *a, int n, int x)
{
int left = 0, right = n - 1;
while (left < right)
{
int mid = left + (right - left + 1) / 2;
if (a[mid] >= x) left = mid;
else right = mid - 1;
}
return left;
}
// 找到第一个小于小于x的数的位置
int bin_search(int *a, int n, int x)
{
int left = 0, right = n - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (a[mid] <= x) right = mid;
else left = mid + 1;
}
return left;
}
一个方便(?)记忆的方法
我们观察两个模板的话，会发现：
如果是 left = mid 的话, mid 就要取右中位值；
如果是 right = mid 的话，mid 就要取左中位值
写二分的时候，可以先把 mid 写成左中位值，再写对应 left 和 right 的操作，最后再看前面的 mid 是否要改成右中位值
lower_bound() 和 upper_bound()
STL 提供了lower_bound(),upper_bound()这两个函数
lower_bound() 返回大于等于所查找数的最小位置
upper_bound() 返回大于所查找数的最小位置
利用 lower_bound() 和 lower_bound() 我们可以实现如下的操作:
- 查找第一个大于等于 x 的元素：
pos = lower_bound(a, a + n, x) - a - 查找第一个大于 x 的元素：
pos = upper_bound(a, a + n, x) - a - 查找第一个等于 x 的元素：
pos = lower_bound(a, a + n, x) - a并且a[pos] == x - 查找最后一个小于等于 x 的元素：
pos = upper_bound(a, a + n, x) - a - 1 - 查找最后一个等于 x 的元素：
pos = upper_bound(a, a + n, x) - a - 1并且a[pos] == x - 查找第一个小于 x 的元素：
pos = lower_bound(a, a + n, x) - a - 1 - 计算单调序列中 x 的个数：
pos = upper_bound() - lower_bound()
注意：对长度为 n 的一段序列查找 x ，如果 x 大于序列中的最后一个数将返回 n
(将上述二分模板中r = n – 1 改为 r = n 的时，会跟上面两个函数一样返回 n)
原文地址：http://www.cnblogs.com/Panmaru/p/16917295.html
