1. 简介
故事分享?：
有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此，图书馆丢了 N - 1 本书。
保安怎么知道只有一本书?没有登记出借，万一全部都没有登记呢？
这个故事其实说出了二分查找需要的条件
- 用于查找的内容逻辑上来说是需要有序的
- 查找的数量只能是一个，而不是多个
比如在一个有序的数组并且无重复元素的数组中，例如[1, 2, 3, 4, 5, 6]，需要查找3的位置就可以使用二分查找。
在二分查找中，目标元素的查找区间的定义十分重要，不同的区间的定义写法不一样
（待补全）
接下来记录三种二分模版：
- 整数二分
//查找左边界 SearchLeft 简写SL
int SL(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
//查找右边界 SearchRight 简写SR
int SR(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1; //需要+1 防止死循环
if (check(mid)) l = mid;
else r = mid - 1;
}
return r;
}一般二分应用于无非下面这四种情况:
1：找大于等于数的第一个位置 （满足某个条件的第一个数）
2：找小于等于数的最后一个数 （满足某个条件的最后一个数）
3：查找最大值 （满足该边界的右边界）
4：查找最小值 (满足该边界的左边界)
而SR和SL分别返回的是满足第一个条件的下标和最后一个条件的下标
eg.有序数组 1 1 2 3 3 4 5 6
用SR和LR分别查找3的位置分别会返回第一个3的位置和最后一个3的位置。
特别提醒：如果使用二分查找查找序列中不存在的数字则会返回数组最后的下标
因为r指针不动，l指针一直更新到r的位置
取中位的写法和注意事项
mid通常是用来进行作为寻找中间值的，通常写法为 (left+right)/2 其实这种写法基本没啥问题，但如果left或right给出数值非常大的数，这样很有可能就会越界，因此会采用以下的写法 移位运算效率是最高的
//不建议
mid =（left+right）/2
//建议
mid =left+(right-left)/2
//移位运算
mid = (l + r+1)>>1 mid若+1，则每次取mid时都是向上取整，可以防止无限循环，但决定因素不止是mid，也和l，r有关。
- 浮点数二分
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double binarySearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}浮点二分 不需要 考虑 向上取整 或 向下取整 。
对于浮点二分来说，调整区间的时候甚至不需要 +1 或 -1。因为是浮点数，+1, -1就可能会错过答案，所以让其等于 mid 自行调整即可。
（待续）