Binary Search

Binary search finds a target in a sorted array in $O(\log n)$ by repeatedly halving the search space.

1. The idea

Binary search requires a sorted (or otherwise monotonic) structure: at each step, compare the target to the middle element and discard half the remaining range based on the comparison, giving $O (lo g n)$ time versus $O (n)$ for a linear scan.

Beyond searching arrays, binary search generalizes to any monotonic decision problem: 'find the smallest x such that predicate(x) is true,' as long as the predicate is false-then-true (or true-then-false) over the search range — common in optimization and simulation-style interview questions.

Careful index handling (avoiding infinite loops and off-by-one errors at the boundaries) is the main practical difficulty, especially when the array has duplicates or you need the first/last occurrence.

2. Why it matters

Binary search is one of the most common building blocks in quant-dev interviews, both directly and as a subroutine inside 'search on the answer' optimization problems.

3. Core mathematics

Time complexity

O (lo g n)

Recurrence

T (n) = T (n /2) + O (1)

Number of halvings to reach 1

⌈ lo g_{2} n ⌉

4. How to recognize it

Think of this when…

Array or range is sorted or monotonic
Asks to find a target value, insertion point, or boundary between true/false regions
Phrased as 'find the minimum/maximum x satisfying a condition'

5. Worked example

Worked example

Given a sorted array of 1,000,000 distinct integers, find the index of a target value using binary search. How many comparisons in the worst case, and what index range does step-by-step search look like for target found at the middle of the second half?

1
Worst-case comparisons is about $lo g_{2} (n)$ .
$lo g_{2} (1, 000, 000) \approx 19.93 \Rightarrow 20 comparisons$
2
First comparison checks index 499999 (middle); if target is larger, search restricts to indices 500000..999999, halving again each step.
$range halves each step$
Answer: At most 20 comparisons are needed, each halving the remaining search range.

6. Common mistakes

Applying binary search to an unsorted array without sorting or establishing monotonicity first
Off-by-one errors in loop bounds (using < instead of <=, or not updating bounds correctly)
Infinite loops from incorrect midpoint updates when low and high converge

7. Quick check

Binary search requires the search space to be:

Worst-case number of comparisons for binary search on n elements is:

8. Practice

2 QuantSolve questions use this concept.

Practice this concept

9. Related methods

This lesson is conceptual; see the topic hub for methods.

Create a free account to save lesson progress.