Binary Search Pattern

All lessons

Learn to recognize when a search space is monotonic — so checking the midpoint tells you which half to discard — and how to avoid the classic off-by-one bugs.

0/5 practice problems solved

Skip to practice

Recognizing the pattern

Reach for it when you need to

the input is sorted, or the answer space is monotonic ("if x works, does x+1 also work?");
you're asked for a specific value, an insertion point, or a boundary (first/last true, minimum satisfying value);
a rotated or partially-sorted array still has one half that's fully ordered;
the brute force is an O(n) linear scan but the search space can be halved every step (O(log n)).

Don't use it when

The data has no monotonic property to exploit — sorting it first may cost more than it saves.
You need every matching element, not just one boundary — a linear scan or two pointers may be simpler.
The 'answer space' framing doesn't have a clean true/false split at every candidate value.
The array is small and unsorted one-off — the overhead of proving monotonicity isn't worth it.

Core mental model

Maintain a search range [lo, hi] where the answer is guaranteed to still be inside it. Check the midpoint: its result tells you, with certainty, which half cannot contain the answer, so you discard that half in one step. The loop invariant — 'the answer, if it exists, is in [lo, hi]' — must hold before and after every iteration, which is what makes halving safe.

Typical time: O(log n)

Typical space: O(1)

Linear scan: O(n)

Visual trace

Search for 9 in [1, 3, 5, 7, 9, 11, 13]. Each step halves the range that could still contain the target.

lo = 0, hi = 6, mid = 3 — nums[3] = 7 < 9, so the answer (if present) is strictly to the right of mid.

lo = 4, hi = 6, mid = 5 — nums[5] = 11 > 9, so the answer must be to the left of mid.

Worked example: Binary Search

nums = [1, 3, 5, 7, 9, 11, 13], target = 9. Halve the range until it converges on the target.

Step-by-step trace of Binary Search
lo / hi	mid	nums[mid]	decision
0 / 6	3	7	7 < 9 → lo = 4
4 / 6	5	11	11 > 9 → hi = 4
Key step: 4 / 4	4	9	found; return 4

Invariant: Before and after every iteration, if the target exists in nums, its index is inside [lo, hi].

Reusable template

The shape to adapt for a new problem in this pattern.

python

def solve(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Common mistakes

Using mid = (lo + hi) // 2 in languages where lo + hi can overflow (not a Python issue, but a habit worth naming out loud).
Off-by-one bounds: lo <= hi vs lo < hi depends on whether hi is inclusive — mixing conventions mid-solution causes infinite loops or missed answers.
Forgetting mid ± 1 and re-checking the same mid forever.
Applying binary search to data that isn't actually monotonic on the property you're testing.
For boundary search (first/last true), returning as soon as a match is found instead of continuing to narrow toward the boundary.

Practice: easy → medium → timed check

Solve in order; each step adds one decision to the same pattern.

1. Binary Search
Easy
Not solved yet
The base template
Solution for Binary Search Practice Binary Search
2. Search Insert Position
Easy
Not solved yet
Boundary search, not exact match
Solution for Search Insert Position Practice Search Insert Position
3. Search in Rotated Sorted Array
Medium
Not solved yet
Find the sorted half first
Solution for Search in Rotated Sorted Array Practice Search in Rotated Sorted Array
4. Find Minimum in Rotated Sorted Array
Medium
Not solved yet
Boundary search on rotation point
Solution for Find Minimum in Rotated Sorted Array Practice Find Minimum in Rotated Sorted Array
5. Search a 2D Matrix
Medium
Not solved yet
Treat a 2D grid as one sorted line
Solution for Search a 2D Matrix Practice Search a 2D Matrix

Final timed check

Run a 30-minute mock covering this pattern; state the invariant before coding, then finish with complexity and edge cases.

Start timed mock

Next lesson

Tree Traversal

Continue