本文正在参加「金石计划」
二分查找背模板？我挑选去理解它！：根底篇
本篇文章是自己学习二分时的一些理解，文章较为烦琐诙谐，假如各位急于学习的话能够直接移步到第四节的部分，看完你一定会有所收获
零、序文——留意看，眼前的这个男人叫
小帅，他正打算和旁边的小美一同玩一个游戏，这个游戏叫猜数字，规则如下：一个人想一个0到100的数字，然后另一个人来猜，依据那个人猜的数字回应他大了、小了和正正好，看看谁猜出来数字所用的次数最少。
小帅是个老实人，它从0开端一个个的猜，这样必定能猜到正确的答案，不过小美想的数字是78，小帅猜了79次才猜到。
小帅为了不输，所以他想的数字是79——比78大一点点，他认为这样就能够赢过小美了。
可是咱们大女主小美一点都不care，她只用了6次就猜出了正确答案，降维冲击！
她会读心吗？开挂了？运气好？
咱们来看看她是怎样猜的。
她第一次猜的数字是50，小帅答复小了。
她第2次猜的数字是75，小帅答复小了。
她第三次猜的数字是87，小帅答复大了。
她第四次猜的数字是81，小帅答复大了。
她第五次猜的数字是78，小帅答复小了。
她第六次猜的数字是79，小帅答复正正好。
是的，相比较小帅的老实人操作，小美用了一点点的办法。
小美的做法是有依据的，她每次都只问最中心的那个数，那么每一次，依据小帅的答复过大或过小，她都能够扫除去一半的过错答案。
比方第一次小美猜的50，小帅答复小了，那么很明显，0到50间的所稀有咱们都不必去猜了，答复必定都是小了。
那么接下来咱们就只用从51到100之间猜数了。
至于0到50的数，咱们将它们扫除了。
像这样，每次都扫除去区间内一半的答案，最坏的状况下，咱们也只用8次就能够猜出正确答案了。
至于像这样这样每次查找中心的元素，再依据反馈不断缩短区间的办法，就叫做：
一、知道知道它吧——二分查找
二分查找，也叫折半查找，它被广泛的用于在特定的环境下快速找到某一元素，常见的状况便是：在一个有序数组中查找目标值。
当咱们在一个区间内查找答案时，每次都查找位于区间中心的元素，然后依据查找的元素和目标值的联系逐渐缩短区间。
由此能够做到，每一次查找时，都能够扫除去一半的过错答案，那么关于一个长度为n的数组来说，只需求最多
次就能够找到目标值的方位了。时刻复杂度就为：
而正常状况下，在一个数组内查找元素，假如咱们挑选遍历数组的办法来查找，它的时刻复杂度为：
在刚刚的游戏中，小帅运用的便是遍历数组的方式，而小美运用的是二分查找法，谁的功率更高，高低立判。
好的，现在二分查找的原理你现已知道了，是不是很简略？
不过，二分也并不是万能的！它是有自己的局限性的！
那么，就让咱们来看看——
二、啥时候能用二分呢
刚刚咱们在介绍二分时说了：“它被广泛的用于在特定的环境下快速找到某一元素。”
这个特定要留意了。
二分不是什么时候都能用的，就比方说假如咱们想要在数组中查找特定值，就必须要确保这个数组是有序的（逆序或正序无所谓，有序就行），假如数组不是有序的状况下，咱们去运用二分查找，会使得咱们得到的成果是过错的。
比方：
1 5 4 8 9
我想找5在哪个方位，我先枚举中心的方位，是4。
发现小了，那么我要往右边找。
但咱们发现此刻答案就现已不对劲了。
由此可知，这个特定的环境不能少啊！（拍桌）
那么什么时候算特定的环境呢？
依据我个人的经历，假如一个题目的答案具有单调性，那么就能够运用二分查找。
什么是单调性呢？
从某一个分界点开端，答案分成了前后两个不同的部分，且这两部分的答案不会紊乱，此刻咱们要做的便是找到这个分界点。
在正常的二分查找中，单调性体现在目标值和数组中数字的大小联系。
比方刚刚猜数字，他猜的是x，那么在x之前的数，答案都是小于x，在x之后的数，答案都是大于x，没有说x之后有哪个数是小于x的，这便是答案的单调性。
在二分答案（二分查找的另一种用法）中，单调性体现在最大、最小、恰好等字眼中。
比方去买东西，不知道要多少钱才能够买完我想要的悉数东西，要求出最少需求的钱数，它便是分界点。比它大的钱数都能确保钱够买完咱们想要的东西，比它小的钱数则都买不完。
而答案紊乱便是指咱们上面举的数组非有序的例子，分界点5之后的所稀有并不都是大于5的，这样答案就失去了单调性，此刻运用二分查找是过错的！
所以切记，二分查找虽好，可不要乱用噢。
二分查找的运用条件咱们现已知道了，那么接下来让咱们——
三、来看看代码是怎样完成的
这儿先给出二分查找的两种模板代码。
（留意，二分的模板有许多种写法，依据不同人的喜好运用不同的办法，我这儿写的是我个人比较喜欢用的）
//查找数组中第一个大于x的元素
while(l<r)
{
int mid=(l+r)/2;
if(a[mid]<x)l=mid+1;
else r=mid;
}
//查找数组中最终一个小于等于x的元素
while(l<r)
{
int mid=(l+r+1)/2;
if(a[mid]<=x)l=mid;
else r=mid-1;
}
总共也就四行代码。以上变量的意思是：
l:区间的左端点。
r:区间的右端点。
mid:每次咱们枚举的，区间中心的方位。
a[]:数组。
x:目标值。
就像咱们说的，每次咱们都枚举的是中心的元素，所以mid=(l+r)/2，然后经过if判别目标值和咱们当时枚举元素的联系，来决定是修正区间的左端点l，仍是修正区间的右端点r。
现在感觉确实很简略有没有？
不过！正当一个小萌新决心满满的开端用它去写题时，意外发生了！
“啊？为什么超时啊？不是说这个算法很快吗？”
“啊？？为什么这个while它停不下来啊？”
“啊？？？为什么这个答案是错的啊？”
“算啦！我仍是把代码背下来吧！横竖都能用！”
“嗯？？？？怎样这儿+1，这儿又-1，这儿又不变的？”
“搞什么鬼啊啊啊啊啊！！！！”
是的！咱们的小萌新惨遭滑铁卢啦（哈哈哈哈哈）！
至于让咱们的小萌新感到如此抓狂的，便是令人破防的边界问题！
在咱们学习二分查找的过程中，多多少少都应该遇到过上面小萌新的状况，二分算法尽管是初级算法，可是是许多算法初学者的噩梦，甚至有的许多学到很后边了的，也搞不清二分的边界问题。我其时也是深受其害呀。
而当你想背下代码直接用时，发现背着背着如同有点紊乱？
而且二分是很灵敏的！不同的状况下，二分查找都有不同的写法，光靠背真的很难受啊！
而且关于想挑战程序设计比赛的同学们来说，知道一个知识点，背下它的代码有时候真的不是很便利。
程序设计比赛麻烦的不是一个知识点，而是怎么把一个知识点玩出花来。
有时候看看大佬们的题解，就会不由得惊叹： “啊？这个还能这么用吗？”
所以！（再次拍桌）
比起愣愣的记下代码，我挑选——
四、背什么？掌握它！——这一段会有点长，但绝对简略易懂，不骗你！
咱们来看看刚刚给出的两个模板。
//查找数组中第一个大于x的元素
while(l<r)
{
int mid=(l+r)/2;
if(a[mid]<x)l=mid+1;
else r=mid;
}
//查找数组中最终一个小于等于x的元素
while(l<r)
{
int mid=(l+r+1)/2;
if(a[mid]<=x)l=mid;
else r=mid-1;
}
来！咱们来玩找不同！
看看这两个代码有几处不同呢？
很明显的看出，有四处：
1、当时所枚举的元素
int mid=(l+r)/2
or
int mid=(l+r+1)/2
2、缩短左区间
l=mid+1
or
l=mid
3、缩短右区间
r=mid
or
r=mid-1
4、判别条件
a[mid]<x
or
a[mid]<=x
总的便是这么四种状况，确实，有点乱，不过好在其他的当地都没有问题啊。
去掉那几个状况后，代码的模板就变成了：
while(l<r)
{
if()
else
}
尽管如同也不剩啥了，可是不急！
从现在开端，咱们一步一步的还原这个代码！
在咱们还原代码时，咱们要先记下一个操作：
咱们要一直确保正确的答案在咱们的区间[l，r]中，（包含l和r的方位）
好，现在咱们要想一个运用二分的环境，就挑选：在升序数组中找第一个大于等于x的值的方位。
那么首要的，咱们必定是要枚举区间中心的元素。
咱们加上：
while(l<r)
{
//先不论这儿+不+1，横竖咱们都是要枚举中心元素的，至于+1的问题咱们后边讲
int mid=(l+r)/2
if()
else
}
好的，现在咱们现已枚举了一个元素，这个元素只可能有两种状况：大于等于x 和 小于x。
随便选一种状况放入 if 中，就当他大于等于x吧，咱们把这个写上：
while(l<r)
{
int mid=(l+r)/2
if(a[mid]>=x)
else
}
咱们要找的是第一个大于等于x的值，而现在，咱们枚举的元素确实是大于等于x的。
可是咱们并不知道这个元素是不是第一个。
那么很显然的，想知道是不是第一个，咱们就去它的左面看看有没有比他更早大于等于x的元素。
假如有，它就不是第一个了；反之，它便是第一个，也便是咱们要找的答案。
但不论怎样样，它右边的元素咱们必定不必找了，他右边的元素怎样可能比他还早大于等于x呢？
所以咱们这儿要做的是缩短右端点，即修正r的值。
问题来了！这儿是写 r=mid ?仍是 r=mid-1 。
尽管咱们现在不知道枚举的这个元素是不是答案，但它也许是对的。（毕竟假如右边没有比他更早一步的元素，它便是答案了）
那么咱们称它是一个：可能的答案。
假如咱们挑选了 r=mid-1，会发生什么事？咱们把这个元素去掉了！
回想我一开端说的：
咱们要一直确保正确的答案在咱们的区间[l，r]中，（包含l和r的方位）
假如咱们挑选了r=mid-1，那就会去掉一个可能正确的答案，所以咱们不要这么干。
所以很显然，这儿咱们要写的当然是r=mid:
while(l<r)
{
int mid=(l+r)/2
if(a[mid]>=x)r=mid;
else
}
假如咱们枚举的这个元素是小于x呢？
它不满意大于等于x，是一个过错的答案。
而且它左面的所有元素都是过错的答案，此刻咱们就要缩短左端点，即修正l的值，来扫除过错答案。
那么这儿咱们是挑选 l=mid ?仍是 l=mid+1 。
再次看咱们上面的那句话。
咱们只要确保正确的答案在咱们的区间中就能够了，而这个答案明显是一个过错的答案，那么咱们当然能够顺手把他去掉啦。
所以咱们这儿写的便是l=mid+1.
while(l<r)
{
int mid=(l+r)/2
if(a[mid]>=x)r=mid;
else l=mid+1
}
那么现在，有问题的当地就剩余一处了，便是mid那里到底要不要+1？
关于这个问题，咱们首要想到的应该是：为什么会有+1这个操作？
这儿先说一下，这个+1，其实是一个手动四舍五入的过程。
咱们这儿进行的是整数除法，而咱们知道，整数的除法会主动去掉尾部的小数，而不是帮你四舍五入，比方：(3+4)/2得到的是3而不是4。
而当咱们+1后，本来偶数的运算变成奇数了，可是成果没有变化；本来奇数的运算变成偶数了，成果+1。
假如把它放在咱们的程序里，表明的含义便是咱们枚举元素时，更容易枚举到一个倾向右边的元素。
- 假如区间端点相加(l+r)是偶数，那么枚举的方位便是正中心，没有问题。
- 但当区间端点相加是奇数，那么枚举的方位就和咱们是否四舍五入有联系了
假如咱们没有四舍五入，枚举的元素便是一个偏左面的元素；
假如四舍五入，枚举的元素便是一个偏右边的元素。
这便是咱们在mid里+1的含义。
那么咱们什么时候+1，什么时候不+1呢？
这一点，要看咱们要找的答案倾向哪个方向。
比方咱们这儿要找的是第一个大于等于x的元素，留意这个第一个。
已然说是第一个了，那么关于咱们来说，这个元素必定越往左越好。由于只要尽可能的往左找，要是找到了大于等于x的元素，那不便是答案了吗？假如咱们尽可能往右找，那么有可能这个元素的左面有比它先一步大于等于x的。
所以，在现在这个状况，答案是倾向左面的。
PS:留意！是倾向左面！而不是答案就在左面！
比方：
1 3 5 7 9 11 13
咱们想在这个数组找第一个大于等于10的元素，那么很明显答案是11，但关于其它大于等于10的元素来说，11确实是 “倾向左面” 的。
所以咱们就不需求给它手动的四舍五入了。
那么咱们的代码就写完了，即：
while(l<r)
{
int mid=(l+r)/2
if(a[mid]>=x)r=mid;
else l=mid+1
}
//if和else是能够相互替换的，无所谓
while(l<r)
{
int mid=(l+r)/2
if(a[mid]<x)l=mid+1;
else r=mid;
}
这便是使用二分查找在升序数组中查找第一个大于等于x的值。
怎样样？有没有茅塞顿开的感觉？？
咱们再来试一试：查找升序数组中最终一个小于x的元素
首要仍是空模板：
while(l<r)
{
if()
else
}
枚举中心元素：
while(l<r)
{
//先不论这儿+不+1，横竖咱们都是要枚举中心元素的，至于+1的问题咱们后边讲
int mid=(l+r)/2
if()
else
}
假如咱们枚举的元素小于x，阐明是可能正确的答案，咱们缩短左区间，即：l=mid.
while(l<r)
{
int mid=(l+r)/2
if(a[mid]<x)l=mid;
else
}
假如咱们枚举的元素大于等于x，阐明是过错的答案，咱们缩短右区间，一起扫除去他，即：r=mid-1.
while(l<r)
{
int mid=(l+r)/2
if(a[mid]<x)l=mid;
else r=mid-1;
}
然后再想一想，答案要找的是最终一个小于x的元素，那么关于咱们来说，这个元素必定越往右越好，咱们在mid处手动四舍五入，即：mid=(l+r+1)/2.
那么咱们的代码就写完了：
//升序数组内查找最终一个小于x的元素
while(l<r)
{
int mid=(l+r+1)/2
if(a[mid]<x)l=mid;
else r=mid-1;
}
//if和else也能够相互互换
//升序数组内查找最终一个小于x的元素
while(l<r)
{
int mid=(l+r+1)/2
if(a[mid]>=x)r=mid-1;
else l=mid;
}
要特别留意！以上我说的两种状况都是在“升序数组”中进行的，假如是逆序数组，则区间的缩短会相反。
以上便是咱们的悉数内容了。
什么？你还有点懵懵的？没事，多看几遍！
那么最终，便是咱们的——
五、结束啦——快乐的韶光总是时间短的呀
总结一下内容便是：
- 二分查找的复杂度为O(logn)。
- 运用二分查找必须要确保答案具有单调性。
- 边界问题要留意，依据详细所求，逐渐分析。
分析代码的四个过程：
- 准备空模板。
- 假如当时枚举的元素满意目标值的联系，区间缩短，但要确保它在区间里呆着。
- 假如当时枚举的元素不满意目标值的联系，区间缩短，能够顺手把它从区间扫除。
- 判别答案倾向左面就不变，倾向右边就+1.
其实这么看下来，二分查找并不磨难呀，但就像我之前说的：
“学习一个知识点并不太难，难的是怎么能玩出花来。”
最重要的仍是多写题积累经历，所以学习完后建议多去找找相关知识点的题来写噢，感受AC的快感。
最终假如本篇文章帮到了您，不知是否能点一个小小的赞呢。（拜托了！这对我真的很重要！）
那么咱们在下一个知识点再会啦！拜拜！
