Binary search but infinite loop

Правка en1, от 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.

Теги binary search

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Singinginginging 2022-01-11 19:46:18 673 Initial revision (published)