cgDude's blog

By cgDude, history, 3 years ago, In English

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;
            }

        
    }
  
}

Full text and comments »

  • Vote: I like it
  • +13
  • Vote: I do not like it