Binary Search Fundamentals

Why interviewers keep asking this

Binary search is the only classic algorithm most candidates believe they already know cold — and it's the one that produces the most live-interview bugs. The idea (halve the search space each step) takes ten seconds to explain. Writing a version that terminates correctly on every input, including size-0, size-1, and size-2 arrays, is a different skill entirely. A Senior-level bar isn't "can you state the algorithm" — it's "can you write it bug-free in one pass while narrating the invariant out loud."

Recognizing the pattern

Binary search applies whenever you can split a search space into two halves and use O(1) or cheap work to determine which half can be discarded. The textbook trigger is a sorted array, but the real trigger is weaker and more general: a monotonic predicate over the index space — a boolean function f(i) that is False for a prefix of indices and True for the rest (or vice versa), with no oscillation in between.

That reframing is what lets binary search apply to structures that aren't obviously "sorted":

• A rotated sorted array (Search in Rotated Sorted Array) — not globally sorted, but at every index one of the two halves is sorted, which is enough to decide which half to keep.
• A unimodal array that strictly increases then strictly decreases (Find Peak Element) — comparing nums[mid] to nums[mid + 1] gives a monotonic "am I still on the uphill side?" predicate.
• A 2D matrix sorted row-by-row and column-by-column (Search a 2D Matrix) — treat it as a single sorted sequence of length m * n and binary search over a virtual 1-D index.

If you can articulate the predicate in one sentence, you can binary search on it. This same reframing is the entire idea behind the next subtopic, Binary Search on the Answer Space — the only difference there is that the search space is a range of candidate answers instead of array indices.

The loop invariant, precisely

Every correct binary search maintains an invariant of the form: "if the answer exists, it is currently within [lo, hi]." Every loop iteration must narrow this range while never accidentally excluding a valid answer. Three canonical templates cover essentially all interview variants:

Template	Interval convention	Loop condition	Use case
Exact match	[lo, hi] inclusive	while lo <= hi	"Does target exist, and at what index?"
Lower bound (leftmost True)	[lo, hi) half-open	while lo < hi	"First index where predicate becomes true" / insertion point
Upper bound (rightmost element <= target)	[lo, hi) half-open	while lo < hi	"Last index where predicate is still true"

The lower-bound template generalizes cleanly: an upper-bound search is just lower_bound applied to the negated/mirrored predicate, and Python's bisect_left / bisect_right are production implementations of exactly this template.

Complexity

• Time: O(log n) — each iteration halves the search space, so at most ⌈log₂(n + 1)⌉ iterations run.
• Space: O(1) for the iterative form. A recursive implementation is O(log n) space due to call-stack depth — a common "can you avoid the extra space?" follow-up.

If you additionally do O(n) work per iteration (e.g., counting matrix entries <= mid), the total becomes O(n log n) or O(n log k) depending on what k bounds — always state this compound complexity explicitly rather than reflexively saying "O(log n)."

The four classic bugs

Bug	Symptom	Fix
Wrong loop condition (< vs <=) mismatched with interval convention	Infinite loop or off-by-one miss at boundary	Closed interval [lo, hi] → while lo <= hi. Half-open [lo, hi) → while lo < hi. Never mix them.
hi = mid in a closed-interval search	Infinite loop when lo == mid and hi never shrinks	In [lo, hi], rejecting the left half must be hi = mid - 1, not hi = mid.
mid computed as (lo + hi) // 2	Integer overflow in fixed-width-int languages (Java, C++) on huge index ranges	Use lo + (hi - lo) // 2. Harmless in Python (arbitrary precision), but say it out loud anyway — interviewers listen for this.
Rightmost/leftmost mid rounding	Infinite loop specifically when hi == lo + 1	For a "keep the right candidate" search (lo = mid), round mid up: mid = lo + (hi - lo + 1) // 2, otherwise mid can equal lo forever.

The single highest-value habit: before coding, say the invariant out loud — "lo and hi are both valid candidate answers at all times" or "the answer is always in [lo, hi)" — and check that every branch preserves it. Interviewers at a Senior bar are explicitly listening for this narration, not just correct code.

Edge cases to test out loud

• Empty array (n == 0).
• Single-element array, target present and absent.
• Target smaller than every element / larger than every element (insertion at the boundaries).
• Duplicate values, when the problem asks for the first or last occurrence specifically (this is precisely what the lower-bound/upper-bound distinction is for).

Where this goes next

The "sorted array, find a value" version above is the easy half of this subtopic. The harder, more distinctive interview skill — extending a monotonic predicate to structures that don't look sorted at all (rotated arrays, unimodal arrays), and then to abstract answer spaces with no array in sight — is what the rest of this topic and the next subtopic build on. You'll also meet this idea again inside the Trees topic, where a Binary Search Tree is essentially binary search materialized as a data structure instead of an algorithm over an array.