Binary search

Given a sorted array of distinct integers and a target, return the target's index, or -1 if it is absent. The algorithm must be O(log n).

Before you code

Write down what lo and hi mean before writing the loop. With a half-open range a[lo:hi], the loop condition and both updates follow from that choice.

Hints

1. Start with lo = 0 and hi = len(nums), and loop while lo < hi.
2. Compute mid = lo + (hi - lo) // 2.
3. Too small: lo = mid + 1. Too big: hi = mid. Equal: return mid.
4. Test an empty range, one element, and targets below the first and above the last element.

Production & complexity notes

When solving Binary search on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Binary search without off-by-one bugs to reinforce the underlying pattern.

What it practices

A binary search you can trust, from Binary search without off-by-one bugs.