Given a sorted array and a target, return its index, or the index where it would be inserted to keep the array sorted.
Getting the loop invariant and boundaries right — the #1 source of bugs.
Classic halving. Use lo ≤ hi and mid = lo + (hi−lo)/2 (avoids overflow in other languages; `>> 1` floors it). When the loop ends, `lo` is exactly the insert position — the point where the target would go to keep order. Master this template; every binary search is a variation of it, and the bugs almost always live in three places: the loop condition (`<=` vs `<`), how you move the bounds (`mid+1` / `mid−1` vs `mid`), and what you return when not found. Fix a consistent invariant ('answer is in [lo, hi]') and the boundaries follow.
Sorted data + find/insert/boundary in O(log n). Also: any monotonic 'is X feasible?' predicate.
Time O(log n) · Space O(1)