Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Help me with Binary search concept

Revision en1, by cgDude, 2021-02-20 07:48:07

Hi guys I am doing competitive coding for some time now and got quite experience. I want to know while solving binary search problems how you guys get to know whether it would work or not in one go. for me its always trial and error and I always end up in an infinite loop. Is there some fix method and how to know if some method would work or not

int solve(vector<int>&A, int x, int y,int left, int right){
     while(left<right){ // some times here we get (left<=right)
         
        int mid=left+(right-left)/2;
        // watch(mid);
        if(some_condition()){
            right=mid-1; // some people do right= mid here
            
        }
        else{
            left=mid+1;  //some people do left= mid here
        }
        
    }
    return left;
}

Sometimes we write different code too

int solve(vector<int>&A, int x, int y,int left, int right){
     while(left<right){ // some times here we get (left<=right)
         
        int mid=left+(right-left)/2;
        // watch(mid);
        if(some_condition()){
            right=mid-1; // some people do right= mid here
            
        }
        else if(other condition){
            left=mid+1;  //some people do left= mid here
        }
        else{
            return mid;
            }

        
    }
  
}
Tags #binary search, #algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English cgDude 2021-02-20 07:48:07 1402 Initial revision (published)