什么是二分查找
二分查找通俗講就是在一個已經排好序的陣列中找答案的范圍，每次取范圍的中間值，如果這個值大了，就取前一半繼續縮小范圍；如果這個值小了，就取后一半縮小范圍，
經過每一次都可以縮小1/2的范圍，逐漸得到答案，
錯誤邊界樣例
例題：https://www.acwing.com/problem/content/description/1229/
這題很明顯可以用二分，列舉1到100000的情況
設l=1,r=1e5,mid=(l+r)/2;
以前我一直都是如果mid小了就l=mid+1；mid大了就r=mid-1,但是當這題答案為5時，就會答案錯誤，為什么呢？
如圖，每行第一個為l，第二個為r，第三個為mid
如果此題答案為5，當mid=4時，l=mid+1,即l=5，就退出了回圈，最后答案為4，
邊界
（1）mid=(l+r)/2時，其實是(l+r)/2的向下取整，當l=mid,r=mid+1時，如果l+1直接退出回圈，而r=mid+1這個值都沒有取到過，
由于是向下取整，即l <= mid < r，所以mid始終是取不到r的值，可以改成mid大了就r=mid，即
while(l<r){
int mid = (l+r)/2;
判斷成立陳述句;
if(滿足條件){
ans=mid;
l=mid+1;
}
else{
r=mid;
}
}
（2）也可以向上取整，即mid=(l+r+1)/2，同理，l < mid <= rmid始終不會等于l，這時可以改成mid小了就l=mid，可得代碼
while(l<r){
int mid = (l+r+1)/2;
判斷成立陳述句;
if(滿足條件){
ans=mid;
l=mid;
}
else{
r=mid-1;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/253566.html
標籤：其他
上一篇：Win10應用清單(自用)