# 二分查找万金油模板
- 自己写二分查找为什么老是死循环呢？
- 缩小区间的时候，左边界是否为+1还是不加1？有边界是否-1还是不减1？
- 迭代的终止条件cl < r 还是 l <= r?
如果你也遇到过上面的疑问？那么恭喜你，你已经打败了50%的人了。因为你并没有安于现状！直接去调用别人写好的接口。你想搞懂它的底层逻辑。那这种求知欲会让你未来的程序生涯一片光明！
给定一个单调不降的数组。求>6的最小的那个数的下标。如：[1,3,4,6,6,6,7,8,9]那么大于6的就是这个7.这个7对应的下标就是6。如果没有学过二分查找。最暴力的方法就是从前往后遍历。从第一个元素开始，一个一个的往下去找。直到找到一个大于6的那个数。然后返回这个下标就完事了！这中方式的时间复杂度是O(n)。数组越长，耗时越久。效率也就越底下！
如果到这里你还能听懂，那恭喜你已经打败了80%的人。
接下来我们开始引入二分查找的概念。由于这个数组[1,3,4,6,6,6,7,8,9]是一个单调不降的。所以把这个数组分层二个部分。一个红色区域。红色区域代表不满足目标条件的元素。另外一个是绿色区域。绿色区域代表满足条件的元素。比如这个问题的条件是大于6.那么所有不大于6的标记成红色。所有大于6的标记为绿色。而我们要找的就是红色与绿色的边界。而对于这个问题我们要找的是什么呢？是第一个绿色元素的下标。那么如果到这里你还能听懂呢？说明你有一个抽象问题的能力！因为图像往往比数字更能让人理解。你会发现原本是一些数字现在我把这些数字转化成了图像。——能够抽象出这一层。那么恭喜你你已经打败了90%的人了！
接下来，我们要想一个办法找到这个边界。怎么找到这个边界呢？
答：我们可以设定二个游标。一个是红色游标。一个是绿色游标。
红色游标：初始化在数组最左边。
绿色游标：初始化在数组的最右边。
然后想办法让二个游标不断逼近。最终的目的是为了让红色游标停留在最后一个红色元素的位置。让这个绿色游标停留在第一个绿色元素的位置。那具体怎么样让二个游标往中间靠拢呢？我们只要找到二个游标的中心点。然后去判断中心点到底是在绿色还是在红色？因为我们先前有一个条件。这个条件就是绿色游标始终在绿色位置。红色游标始终在红色的位置。所以如果中间点还是红色的。那么我就把红色游标往中间点靠拢。反之则把绿色游标往中间靠拢。而每一次操作这个游标，都会干一件事情。就是把这个区间缩小。而且每一次区间都缩小一半。这样一来。经过log(n)次缩小操作以后。这件事情就做完了。如果到这里还能听懂。那么恭喜你打败了95%的人了。
现在问题来了，假如说所有的元素都是不满足条件。那是不是这里的元素都是红色？既然都是红色。我一开始的那个绿色游标初始化的时候就在红色位置。那不是不对了吗？想一下？也就是说我初始化的时候已经不满足条件了。这可怎么办呢？这里逻辑存在问题了。所有我们要虚拟出二个位置来。这二个位置叫哨兵。——就是初始情况下红色游标和绿色游标都在数组都外面。这样就可以避免数组是全红或者全绿的情况。我就能保证任何时候游标所在的位置都是合法的。——经典的红绿灯模型。如果到这里还能听懂。那么恭喜你打败了96%的人了。
最后我们要确定终止的条件。二个游标所组成的区间是不断在缩小的。什么时候不用在往下缩小了呢？基于二个条件。
第一个条件：红色和绿色游标永远不能重合。因为任何一个位置都不可能同时是红色同时是绿色吧。
第二个条件：红色游标永远在红色位置，绿色游标永远在绿色位置
最终情况下是：
红色游标在最大的红色位置。而绿色游标在最小的绿色位置。也就是 l + 1 == r的时候程序结束掉。
我的终止条件是r，那么在某一个情况下会不会变为1？答：不会。
二分查找的模板：
int binSearch(int *arr,int n,int x){
// 初始游标的位置
int l = -1,r = n;
int mid;
// 迭代的终止条件
while(r - l > 1){
// 中点的计算
mid = l + (r -1) / 2;
// 依据中点的计算结果移动游标的方式。
if(isCreen(arr[mid], x))
// 右边(绿色游标)移动到中点。
r = mid;
else
// 左边(红色游标)移动到中点。
l = mid;
}
//最后返回绿色元素所在的数组下标值。
return r;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
如果到这里还能看懂代码。那么恭喜你打败了97%的人了。
注意
对于任意道整数类型的二分查找都可以用上面那个模板。区别在于这个 isCreen函数。这个需要根据具体的题目而定了。
# 二分查找万金油模板总结
二分查找具体步骤可以抽象为一下步骤：
第一步：抽象出一个单调的数组或者函数。
第二步：按照给定的条件将它划分成绿色和红色。
第三步：用二分模板找到红绿边界。
第四步：根据找到的边界计算最终值。