二分查找易错分析总结

二分查找易错分析总结 前言：二分分为两种：1.小数二分2.整数二分

小数二分一般比较无脑，因为不用考虑边界问题，但是整数的二分涉及到边界问题就比较容易出错，以下是个人对整数二分的一个总结。

AcWing 789. 数的范围

#include

using namespace std;
const int N = 1e5+10;
int main()
{
    int n,q;
    cin>>n>>q;
    int a[N];
    for(int i=0;i 
 
这道题题意就是：给定一个非递减序列，求第一个大于等于x的数的下标，以及最后一个小于等于x的数的下标。
 
 
求第一个大于等于x的数的下标不容易错，当a[mid]=x的时候，我们可直接将右边界r=mid（这个点比较好理解，就是a[mid]这个数也满足），然后有一个需要留意的点就是：当l+1=r的时候，如果a[mid]>=x的话，由于(l+r)/2向下取整的性质，右边界也会向左逼近，这样就避免了死循环的出现。
 求最后一个小于等于x的数的下标容易出错，当a[mid]<=x的时候，自然地，l=mid，当a[mid]>x的时候，r=mid-1，因为mid这个位置不满足。好像这也是对的，实则不然，如果当l+1=r时，a[mid]<=x，l=mid，**由于（l+r）/2向下取整的特性，l会一直不变，但是循环结束条件是l==r，所以就会导致一个死循环。**究其本质，个人认为是右边界有逐渐向左逼近的趋势，左边界在特殊情况下，却会一直不动，导致了这个问题。
 所以该如何去解决这个问题呢？我们可以回到求第一个大于等于x的下标的方法，它是用(r+l)/2向下取整逼近的性质来“巧合”地解决了这个问题，**我们可以用(r+l+1)/2的方法刻意地向右边界趋近。**这样就解决了这个问题。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5503534.html