The problem
Return the index of a target in a sorted array of distinct integers, or −1 — in O(log n).
Stuck? Reveal hints one at a time
How to approach it
- 1lo = 0, hi = n − 1 (inclusive range).
- 2While lo ≤ hi: mid = lo + ((hi − lo) >> 1).
- 3nums[mid] === target → return mid; smaller → lo = mid + 1; larger → hi = mid − 1.
- 4Exhausted → −1.
Key insight
Every binary-search bug is an invariant violation: decide once what [lo, hi] means, and the loop condition, midpoint, and updates all follow mechanically.
The solution
Watch out for
- lo + (hi − lo)/2 avoids integer overflow in fixed-width languages.
- Mixing inclusive-hi with a lo < hi loop condition skips the last element.