Implement binary search correctly — and explain the off-by-one traps.

How to think about it

Recognise the pattern

Binary search applies any time you have a sorted (or monotone) space and want to find an element — or a boundary — in O(log n) instead of O(n). The pattern extends beyond arrays: it works on answer ranges (“find the minimum feasible value”), on time, even on function outputs.

The signal is: “the space is ordered, and you can cut it in half with one comparison.”

Build the approach step by step

Brute force: scan left to right. O(n) — nothing to optimise for the basic case, but we can do O(log n).

The closed-interval template (find exact target):

Pick a single convention and stick to it. The closed interval [lo, hi] is the most intuitive:

• Loop while lo <= hi (both ends are valid candidates).
• Compute mid as lo + (hi - lo) // 2 to avoid integer overflow (important in Java/C++; Python ints are arbitrary precision, but good habit).
• If nums[mid] == target, return mid.
• If nums[mid] < target, the target is in [mid+1, hi] → set lo = mid + 1.
• If nums[mid] > target, the target is in [lo, mid-1] → set hi = mid - 1.
• If the loop ends without a match, return -1.

Array: [1, 3, 5, 7, 9], target = 7
lo=0, hi=4, mid=2 -> nums[2]=5 < 7 -> lo=3
lo=3, hi=4, mid=3 -> nums[3]=7 == 7 -> return 3

Complexity

	Value	Why
Time	O(log n)	Search space halves each iteration
Space	O(1)	No extra memory (iterative version)

The classic off-by-one traps