Binary search but infinite loop

Revision en1, by Singinginginging, 2022-01-11 19:46:18

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.

Tags binary search

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Singinginginging 2022-01-11 19:46:18 673 Initial revision (published)