Instead of rounding up your mid, you could just tweak the conditions a bit.
1) Use l<=r instead of l<r
2) Update l = mid + 1 and
3) Update r = mid — 1
Skipping the mid when updating is intuitive because you've already processed it.
In the case of l<=r, you need this because your condition won't work when the last [reached] element needs to be processed...

There is no certain way you can prefer a single way while using binary search because in some situations you have to discard mid and in other you can not skip mid just by doing l=mid+1 or r=mid-1.

For figuring this faster, I prefer to follow this way: I imagine only 2 elements. Then I decide to round up mid=(l+r+1)/2 and figure which one to discard and then according to situation I may need to take a situation where it may work rounding mid down (taking floor).

Also, to avoid INFINITE LOOP, I prefer to use for loop of 100 (or logN) iterations that doesn't go infinite and saves a lot of time during contests.

This may seem little hard to do on paper but it is not much difficult to figure out in case of only 2 elements. I hope it helps :)

I had this problem a lot.

In some cases it gave an infinite loop and when I fixed it it gave WA. About observing the test cases , I found that in some cases my answer was one less than the actual answer , hence I manually checked and incremented by one if satisfies the condition.

Here is the template (I have used this in many problems without any issue):-

while(low<high)
{
   int mid = low+ (high-low+1)/2;
   if(condition satisfies for mid) low = mid+1;
   else high = mid -1;
}
// after this loop low==high
if(condition satisfies for (low+1)) low++;
cout<<low<<endl;

Submission

Well, what I do is...

int l = 0, r = n; // being l the number that definitely works, and r the one that definitely does not
while(l + 1 < r){
    int m = (l + r) / 2; 
    (ok(m)? l : r) = m;
}
cout << l << "\n"; // so, here l is the maximum value that holds some propriety

This works since when l + 1 < r, m != l and m != r, and when l + 1 = r , the loop should finish.

Ok so there are two types of binary search:

• There is some condition that works for all $$$i <= x$$$ but not for $$$i > x$$$ and we want to discover $$$x$$$ / the biggest value of $$$i$$$ that satisfies this condition: if we eventually discover that $$$x$$$ is either 2 or 3, we know that the condition is definitely true for $$$i = 2$$$ (because if it wasnt $$$x$$$ could be 1 as well) so we always need to round up to get more information on what is $$$x$$$.

• There is some condition that works for all $$$i >= x$$$ but not for $$$i < x$$$ and we want to discover $$$x$$$ / the smallest value of $$$i$$$ that satisfies this condition: if we eventually discover that $$$x$$$ is either 2 or 3, we know that the condition is definitely true for $$$i = 3$$$ (because if it wasnt $$$x$$$ could be 4 as well) so we always need to round down to get more information on what is $$$x$$$.

Note that for the first type (where the invariant is on the start), since youre always rounding up, it never tests if the condition works for the first value while for the second (where the invariant is on the end) it never tests if the condition works for the last value. Knowing this is useful somtimes for avoiding implementation trouble.

Alternatively you can use std::ranges::lower_bound or std::ranges::partition_point

But you can use this :

		while (R - L > 1) {
			ll mid = L + R >> 1;
			if (f (mid) <= x) {
				L = mid;
			}
			else {
				R = mid;
			}
		}
		if (L > R) swap (L, R);
		ll ans = L;
		if (f (R) <= x) ans = R;
		if (f (ans) != x) ans ++;
		printf ("%lld\n", ans);

And it's Accepted :

136447361

To me this style of binary search is much less error-prone:

int ans = 0;
for (int k = /* some power of two */; k != 0; k /= 2) {
  if (condition(ans + k)) {
    ans += k;
  }
}

It finds the greatest integer with the condition condition. This style is much easier to reason about and adapt to specific cases, without needing to think about rounding up or down while dividing by 2.

Errichto's tutorial tutorial might help.