Binary Search Fundamentals

Binary search finds a target in a sorted array in O(log n) by halving the search space each step. Beyond exact match, its real interview power is finding boundaries — the first/last occurrence, lower/upper bound — and getting the loop conditions exactly right is a notorious source of bugs.

The core idea

Maintain a [lo, hi] window; compare the middle element to the target and discard half. Exact search: if arr[mid] == target return mid; else move lo or hi. For boundary searches (first element ≥ target = lower bound, first > target = upper bound), don't stop at the first match — keep shrinking toward the boundary. Compute mid as lo + (hi − lo) / 2 to avoid integer overflow.

Task	Returns	Time
Exact search	index or −1	O(log n)
Lower bound	first index ≥ target	O(log n)
Upper bound	first index > target	O(log n)
First/last occurrence	boundary of duplicates	O(log n)
Count of a value	upper − lower	O(log n)

Exam Tricks & Tips

• 🎯 Binary search needs sorted (or monotonic) data — always confirm the precondition.
• 🎯 Use mid = lo + (hi − lo) / 2 to prevent (lo + hi) integer overflow.
• 🎯 First/last occurrence: on a match, keep searching the left/right half instead of returning.
• 🎯 Lower bound = first index with value ≥ target; count of x = upperBound(x) − lowerBound(x).
• 🎯 Fix your loop invariant: decide [lo, hi] vs [lo, hi) and keep it consistent to avoid infinite loops.
• ❌ Common mistake: an off-by-one in the mid update or loop condition causing an infinite loop or a missed boundary.

Expected pattern

Search a sorted array, first/last position of a target, count occurrences, search-insert position, or sqrt/ceil via binary search. Interviewers scrutinise the loop bounds and boundary handling.

Quick recap

Binary search halves a sorted range for O(log n) exact or boundary queries (lower/upper bound, first/last occurrence). Use mid = lo + (hi − lo)/2, keep a consistent [lo, hi] invariant, and don't stop early when hunting a boundary.

Cover the answer, recall, then check. 11 cards on binary search fundamentals.

Q1. Binary search time complexity and precondition?
A1. O(log n); the data must be sorted (or monotonic).

Q2. Safe way to compute the midpoint?
A2. mid = lo + (hi − lo) / 2, to avoid integer overflow from lo + hi.

Q3. What is the lower bound of a target?
A3. The first index whose value is ≥ the target.

Q4. What is the upper bound?
A4. The first index whose value is > the target.

Q5. Count occurrences of a value using bounds?
A5. upperBound(x) − lowerBound(x).

Q6. Find the first occurrence of a duplicated target — trick?
A6. On a match, continue searching the left half (record the index, set hi = mid − 1).

Q7. Why do binary searches often infinite-loop?
A7. Inconsistent loop invariants or an off-by-one in the mid/lo/hi update.

Q8. Search-insert position — what does it return?
A8. The index where the target is, or where it would be inserted to keep the array sorted (the lower bound).

Q9. Can binary search work on an unsorted array?
A9. No — but it works on any monotonic predicate, even without explicit sorting.

Q10. Complexity of finding both first and last positions?
A10. O(log n) each, O(log n) total.

Q11. Integer sqrt via binary search — search space?
A11. [0, n]; find the largest m with m·m ≤ n. O(log n).

Binary search is the most powerful O(log n) idea in the toolkit and the most bug-prone to implement. Master the invariant and the boundary handling, and you unlock a whole family of "find the position" problems.

Core idea: on a sorted array, repeatedly halve the search interval by comparing the target to the middle element. Each step discards half the remaining elements, so the search finishes in O(log n) comparisons.

How it works

Beginner — the canonical search

lo, hi = 0, n-1
while lo <= hi:
    mid = lo + (hi - lo) // 2      # avoids overflow
    if a[mid] == target: return mid
    elif a[mid] < target: lo = mid + 1
    else: hi = mid - 1
return -1                          # not found

O(log n) time, O(1) space. The loop invariant: the target, if present, is always within [lo, hi].

Intermediate — lower_bound and upper_bound

The real power is finding boundaries, not just exact hits:

• lower_bound: first index with a[i] >= target (leftmost insertion point).
• upper_bound: first index with a[i] > target.
  These give first/last occurrence, count of a value (upper − lower), and where to insert — all O(log n). Use lo < hi with hi = mid (not mid−1) for the "find leftmost" template.

Advanced — the boundary discipline

Most binary-search bugs are off-by-one. Fix a template and stick to it:

• Inclusive [lo, hi] with lo <= hi and mid ± 1 updates — for exact match.
• Half-open [lo, hi) with lo < hi and hi = mid — for lower/upper bound.
  Never mix them. Always compute mid = lo + (hi − lo)//2 to avoid integer overflow, and make sure the interval strictly shrinks each iteration to avoid infinite loops.

Worked example

Find 7 in [1, 3, 5, 7, 9, 11]. lo=0, hi=5, mid=2 → a[2]=5 < 7 → lo=3. mid=(3+5)/2=4 → a[4]=9 > 7 → hi=3. mid=3 → a[3]=7 = target → return index 3. Three comparisons for six elements; doubling the array adds just one more step — that's O(log n).

When to use it

• Search in any sorted array, or find insertion position, first/last occurrence, count of a value.
• As a subroutine: search in rotated arrays, 2-D matrices, "binary search on the answer" (next topic).
• Any monotonic predicate: "find the smallest x where condition(x) is true".

Tricks & gotchas

• Use mid = lo + (hi − lo)//2, never (lo + hi)//2, to prevent overflow in other languages.
• Pick one template (inclusive vs half-open) and never mix boundary updates.
• Ensure the interval shrinks every iteration — a stuck lo == mid with lo = mid loops forever.
• Mnemonic: "Halve the interval; keep the target inside [lo, hi]."

Key formulas

• Requires a sorted array; T(n) = T(n/2) + O(1) ⇒ O(log n).
• Iterations ≈ ⌊log₂ n⌋ + 1; space O(1) iterative, O(log n) recursive.
• Invariant: target lies within [lo, hi]; mid = lo + (hi − lo)/2 (avoids overflow).
• Lower bound (first ≥ x) and upper bound (first > x) variants.
• Off-by-one care: choose [lo, hi] or [lo, hi) consistently.

Usage: keep the loop invariant explicit to get the boundary conditions right.

Worked Example

Problem: Search for 23 in the sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0–9) using binary search.

Solution: Compare the target with the middle element and discard half the range each step.

lo	hi	mid	a[mid]	vs 23	action
0	9	4	16	16 < 23	lo = 5
5	9	7	56	56 > 23	hi = 6
5	6	5	23	equal	found!

Target 23 is at index 5, found in 3 comparisons.

Each step halves the search space, so binary search is O(log n) — but it requires the array to be sorted.

Answer: Found at index 5.