Binary Search — O(log n) on sorted data

Precondition: the array is sorted (or you can sort it, which is O(n log n)). Repeatedly halve the range until you converge.

Rules to write it correctly

1. Invariant — decide what lo and hi mean:
   • Inclusive both (lo <= hi, hi = mid - 1) — most common.
   • Half-open (lo < hi, hi = mid) — better for "find boundary" problems.
2. Termination — pick a loop condition that makes the search shrink each iteration or you have an infinite loop.
3. Avoid overflow — in Python you don't have to, but in C/Java use lo + (hi - lo) // 2 not (lo + hi) // 2.

Beyond simple search: binary search on the answer

This is the interview-power-move. When you're asked "find the minimum X such that Y holds" and Y is monotonic in X (once true, stays true), binary search the value of X.

Examples:

• Smallest ship capacity to deliver in D days
• Minimum time for K workers to complete tasks
• Minimum spice level everyone can eat

The predicate is a helper function; the outer loop is a binary search over the answer space.

Off-by-one traps

• Empty array — check upfront or ensure the loop handles lo > hi.
• Duplicates — plain binary search returns some index. If you need the leftmost or rightmost, use the boundary variant.
• The +1 on lo and -1 on hi — miss it and you loop forever.

Try it

1. Write search_range(nums, target) that returns (leftmost_idx, rightmost_idx) of target, or (-1, -1).
2. Given a list of ship capacities and D days, use binary-search-on-the-answer to find the min capacity that finishes in D days.