Hey I found this implementation on a codeforces blog. What do you think about it , is this the most easy and reliable implementation according to you (for solving the problems)? I am asking because there's so much confusing stuff about loop invariants and I just want something which always works for sure!

```
l, r = -1, n
while r-l > 1:
m = (l+r)//2
if F(a[m]):
l = m
else:
r = m
```

You can easily prove that l = k and r = k + 1 by the end of the while loop. In this case no worries about whether to increase m by 1 or not.

Yes, it is very easy implementation and it can be used, in cycle

mcan get values only from 0 ton- 1, it has not yet failed me. For example, this problem and solution using binary search.UPD: And in this problem tooReliable? Yes.

Easy? Depends on whether you like [l, r] or [l, r). Personally I prefer [l, r] implementations over this, it's easier to do / think about.

If we know the range then any implementation can be used right? For example: if answer lies in [l,r) then the above implementation can be used with l=l-1 and r=r ?

The above implementation is [l, r), and that is perfectly fine.

I am just stating a matter of preference, because I make less bugs when I use [l, r].

I think it's even simpler than that. After the "while" loop you know that correct answer is either "l" or "r" so you can check both by calling function "F" on them again and take smaller/larger (depending on what problem is asking for). I've seen that in codes of some really good coders.

Personally I don't like that approach, but who cares. If it works for you then, well... it works for you :)

Oh you so have to check the l(or r) at last...I haven't encountered a problem yet where the ans doesn't lies in the search space hence was not doing that! Thanks

No, I'm not talking about that. You are left with 2 values, "l" and "r", so you don't know the exact solution (is it "l" or "r"). Therefore you have to calculate "F" again for both of them.

I thought if the answer lies to left of mid then it should be 'l' but if the answer lies to right then it should be 'r'. The given implementation thus can give l,r == k,k+1 or l,r==K+1,k where k is the point where the function changes.

So if we always shrink the search space to the right of mid then the answer should be in 'r' (similarly for 'l')

I don't understand when it gives confusing answer, can you give a example of such a case?

Sorry, I was wrong. Only case when it's like that is when you have l == r — 1 at the start, but that's just some corner case.

Hmm for such case (i.e. when l==r-1) we have only two values in the search space so we have to compute the function for both values. Thanks this discussion helped me a lot :)

`no worries about whether to increase m by 1 or not`

Good luck! I hope this helps.