Binary search on the answer, without the off-by-one

Most binary search bugs aren't in the comparison. They're in the loop boundary, and they come from writing the loop before deciding what the invariant is.

Decide what's true, then write the loop

Binary searching on the answer means you have a predicate that's false for a while and then true forever:

f f f f f t t t t t
          ^ the answer

You're looking for the first t. So maintain exactly this invariant:

• lo is always a position that could still be the answer
• hi is one past the last candidate

int lo = 0, hi = n;           // answer lives in [lo, hi)
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (ok(mid)) hi = mid;    // mid works, so nothing past it matters
    else         lo = mid + 1; // mid fails, so the answer is strictly after
}
// lo == hi == first index where ok() is true

Two details that remove most of the pain:

• lo + (hi - lo) / 2 instead of (lo + hi) / 2 — the second overflows once the bounds get near INT_MAX.
• The half-open range [lo, hi) means the loop ends with lo == hi and no final "which one is it?" check.

The part people skip

ok() has to be monotone: once it's true it stays true. If it isn't, binary search doesn't merely give a wrong answer, it gives a confidently wrong one.

Before writing the loop, say out loud why the predicate can't flip back. If you can't, the problem probably isn't a binary search.

Complexity

$O(\log n)$O(logn) calls to ok(). If ok() is itself $O(n)$O(n) — which it usually is when you're binary searching on an answer — the total is $O(n \log n)$O(nlogn), and that's normally the intended solution.