Hi I always have some problem on coding binary search
int l=1,r=n-1;
while(l<r){
int mid=(l+r)/2;
if(/*condition*/)l=mid;
else r=mid-1;
}
This may seems ok, but this is wrong, as there may be a infinite loop.
int l=1,r=n-1;
while(l<r){
int mid=(l+r+1)/2;
if(/*condition*/)l=mid;
else r=mid-1;
}
with the mid rounded up, this will not give a infinite loop.
Is there a way to memorize this? I don't want to debug my binary search in contests, which takes a long time.