Help me with Binary search concept

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

        
    }
  
}
Теги #binary search, #algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский cgDude 2021-02-20 07:48:07 1402 Initial revision (published)