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;
}
}
}
A good technique:
if you are looking for 1st position satisfying some condition do this:
mid=(left+right)/2;
if(some_condition()) left=mid+1;
else right=mid;
if you are looking for last position satisfying some condition do this:
mid=(left+right+1)/2;
if(some_condition()) left=mid;
else right=mid-1;
Check this recent blog, it goes through all your questions. Where to use what is implementation dependent make sure, you don't confuse two or more ways.
I come up with the following rules:
Suppose that the array b is sorted in an increasing order, and we are going to find the maximum value that is less than some fixed value X.
At first, check b[0] and if b[0] >= X, then finish since no answer could be found, while if b[0] < X, it means that b[0] might serve as the answer. Then, we take L = 0 and R = n-1 (n is the length of array b), and note that during the binary search, we always keep the borders with a form of [L, R), where L is "included" while R is "excluded", meaning that index L always satisfies while index R is not known yet but going to be checked. Thus, the middle index should be M = (L + R + 1) / 2, and if b[M] < X, then L = M, since M is known to satisfy the condition while if b[M] >= X, then R = M-1, since M is known to not satisfy the condition but M-1 is not known yet. Here are codes:
Similarly, if we are asked to find the minimum value which is larger than some fixed value X, the codes go like:
Here we use (L + R) / 2 instead of (L + R + 1) / 2, since in this case we "have (L, R]".
You should once look into EDU section tutorial on binary search. Its one of the best binary search resources i know