Please read the new rule regarding the restriction on the use of AI tools. ×

Gordon-Freeman's blog

binary search
By Gordon-Freeman, history, 5 hours ago, In English

Can someone explain to me how do we choose ranges when doing BinarySearch i solved a lot of BS problems but to be honest i alwayes try differnt ways until one of them work... by mean whats the diffence between writing while(l<r) and while(l<=r) and while(l+1<r)...etc and when do we set r=mid and when r=mid-1 and same for l , please someone explain them all this is the only thing confuse me at BS problems

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

»
4 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This is how I usually approach the binary search implementation.

First, I define an invariant for the pointers. For example, in some cases, I want to ensure that the left pointer (l) always points to a position that is strictly less than the answer, while the right pointer (r) should always be greater than or equal to the answer.

This approach is useful in cases where we want to find the lower_bound() of the answer, meaning the first element that is greater than or equal to x.

Based on that, I use the following implementation:

The initial value of l should satisfy < f(l) == false, meaning l points to a value less than the answer. The initial value of r should satisfy >= f(r) == true, meaning r points to a value greater than or equal to the answer. Next, I use the condition while (l + 1 < r). This ensures that when the loop exits, l and r are adjacent (l = r - 1), and we can determine that r will be the first element that is >= x.

To calculate the midpoint, I use:

int mid = (l + r) / 2;

if(f(mid)){
	r=mid; //this is because we know that mid is >= ans. But we dont know about mid - 1
}else{
	l=mid; // we know mid < ans
}

When the algorithm finishes you will have in r the first element >= x.

The main idea is to set that invariant (l < answer, r >= answer) and then the implementation gets easier.

This is how I approach BS problems. Correct me if there are any errors

→ Reply