Pattern 06 · Search

Binary Search

Eliminate half the search space with every comparison. It works on any monotonic search space — not just sorted arrays — turning linear scans into O(log n).

time O(log n)space O(1)templates 3practice 14 problems
01 core concept

Halve it until it's gone

One comparison at the midpoint tells you which half the answer cannot be in — so you throw that half away. Sixteen candidates become eight, then four, two, one: log₂(n) comparisons total.

Search space halving: Step 0: [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16] n=16 Step 1: [1 2 3 4 5 6 7 8] n=8 Step 2: [5 6 7 8] n=4 Step 3: [7 8] n=2 Step 4: [8] n=1 Total steps: log2(16) = 4
1 / 7walkthrough — search for 6 in a sorted array
1lo
3
5
7
9
11
13hi
target 6
candidates 7
Search for 6. The amber range [lo, hi] is the live search space — right now, the whole array.
02 recognition

When to reach for it

  • "Search in a sorted array."
  • "Find the first / last element satisfying a condition."
  • "Minimize the maximum" / "maximize the minimum."
  • "What is the minimum value such that some condition holds?"
  • The array is sorted, or the answer space is monotonic.
Is the array sorted (or search space monotonic)? | +-- YES --> Is there an exact target? | | | +-- YES --> Template 1 (classic) | | | +-- NO --> Looking for a boundary/first occurrence? | | | +-- YES --> Template 2 (lower/upper bound) | | | +-- NO --> Optimization problem? | | | +-- YES --> Template 3 (search on answer) | +-- NO --> Can you define a monotonic condition? | +-- YES --> Binary search still works (e.g., peak element) +-- NO --> Binary search won't help here
When NOT to use it
If the array isn't sorted and you can't define a monotonic condition over the search space, binary search won't help — there's no comparison that safely discards half.
03 critical details

The tricky part

Detail 1Mid calculation

mid.pypython
# WRONG (can overflow in languages with fixed-size ints)
mid = (left + right) // 2

# CORRECT
mid = left + (right - left) // 2

Detail 2Loop condition & boundary updates

Detail Template 1 (exact match) Template 2 (boundary / lower bound)
Loop condition while left <= right while left < right
When to shrink left left = mid + 1 left = mid + 1
When to shrink right right = mid - 1 right = mid
Termination left > right (not found) left == right (answer)
Returns mid (exact), or −1 left (boundary position)
Key insight
In Template 2, right = mid (not mid - 1) because mid itself could still be the answer. Using mid - 1 might skip the answer.
04 templates

The three templates to memorize

T1Classic binary search — find exact target

binary_search.py — LC 704python
def binary_search(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid            # Found it
        elif nums[mid] < target:
            left = mid + 1        # Target is in right half
        else:
            right = mid - 1       # Target is in left half

    return -1                     # Not found

T2Lower bound — first position ≥ target

lower_bound.py — LC 35python
def lower_bound(nums, target):
    """Return the first index where nums[index] >= target."""
    left, right = 0, len(nums)   # Note: right = len(nums), not len-1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] >= target:   # Condition met -- could be answer
            right = mid           # Keep searching left for FIRST
        else:
            left = mid + 1        # Too small, go right

    return left                   # left == right == answer

Upper bound (first position > target): just change >= to >.

1 / 8walkthrough — first index with value ≥ 5
1lo
3
5
5
7
9
·hi
condition nums[i] ≥ 5
Find the first index with value ≥ 5 in [1, 3, 5, 5, 7, 9]. Here hi starts at len(nums) = 6 — the phantom slot — because "no element qualifies" (answer = 6) must stay possible.

T3Binary search on the answer

When the problem asks to optimize a value and you can check feasibility, binary-search the answer space instead of an array.

search_on_answer.pypython
def binary_search_on_answer(lo, hi, is_feasible):
    """
    Find the minimum value in [lo, hi] such that is_feasible(val) is True.
    Assumes: if is_feasible(x) is True, then is_feasible(x+1) is also True.
    (Monotonic feasibility)
    """
    while lo < hi:
        mid = lo + (hi - lo) // 2

        if is_feasible(mid):
            hi = mid              # mid works, try smaller
        else:
            lo = mid + 1          # mid doesn't work, need bigger

    return lo
05 key problems

The problems that keep showing up

P1Search in Rotated Sorted Array — LC 33

Rotated array visualization: Original sorted: [1 2 3 4 5 6 7] Rotated: [4 5 6 7 1 2 3] ---------- ------- sorted sorted half 1 half 2 At least one half around mid is always sorted.
search_rotated.py — LC 33python
def search_rotated(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1   # Target in sorted left half
            else:
                left = mid + 1    # Target in right half
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1    # Target in sorted right half
            else:
                right = mid - 1   # Target in left half

    return -1

P2Find Minimum in Rotated Sorted Array — LC 153

Index: 0 1 2 3 4 5 6 Value: [4 5 6 7 1 2 3] 7 | * 6 | * 5 | * 4 | * <-- "cliff" between index 3 and 4 3 | * 2 | * 1 | * +--+--+--+--+--+--+-- 0 1 2 3 4 5 6 Two sorted segments: [4,5,6,7] and [1,2,3] The minimum is at the start of the second segment.
find_min.py — LC 153python
def find_min(nums):
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:
            left = mid + 1        # Min is in right half
        else:
            right = mid           # Mid could be the min

    return nums[left]

P3Find Peak Element — LC 162

Any neighbor comparison gives a direction toward a peak: * If nums[mid] < nums[mid+1], peak is to the RIGHT / \ If nums[mid] > nums[mid+1], peak is to the LEFT (or mid IS peak) / \ / *
find_peak.py — LC 162python
def find_peak(nums):
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] < nums[mid + 1]:
            left = mid + 1        # Go toward the rise
        else:
            right = mid           # Mid might be peak

    return left

P4Koko Eating Bananas — LC 875 (search on answer)

min_eating_speed.py — LC 875python
def min_eating_speed(piles, h):
    def can_finish(speed):
        hours = 0
        for p in piles:
            hours += (p + speed - 1) // speed   # ceil division
        return hours <= h

    lo, hi = 1, max(piles)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo

P5Sqrt(x) — LC 69

my_sqrt.py — LC 69python
def my_sqrt(x):
    lo, hi = 0, x

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        sq = mid * mid

        if sq == x:
            return mid
        elif sq < x:
            lo = mid + 1
        else:
            hi = mid - 1

    return hi   # hi is the floor of sqrt(x)

Complexity reference

ProblemTimeSpace
Classic binary searchO(log n)O(1)
Lower / upper boundO(log n)O(1)
Search rotated arrayO(log n)O(1)
Find min in rotated arrayO(log n)O(1)
Find peak elementO(log n)O(1)
Koko eating bananas (n=piles, m=max pile)O(n log m)O(1)
Sqrt(x)O(log x)O(1)
06 common mistakes

Where binary search goes wrong

Mistake 1 — off-by-one with right's initialization
len(nums) - 1 vs len(nums) depends on the template. Closed-range Template 1 uses len - 1; half-open Template 2 uses len.
Mistake 2 — the infinite loop
Using right = mid with while left <= right can loop forever. Always pair while left < right with right = mid.
Mistake 3 — wrong half selection in rotated arrays
Forgetting to check which half is sorted first. Test nums[left] <= nums[mid] before deciding where the target can live.
Mistake 4 — integer overflow
(left + right) // 2 overflows in languages with fixed-size ints. Use left + (right - left) // 2 everywhere, even in Python, as a habit.
Mistake 5 — forgotten edge cases
Empty array, single element, all elements the same. Walk your template through n = 0 and n = 1 before submitting.
07 search on the answer

Guess a value, ask "is this feasible?", shrink the range

In the hardest binary-search problems there is no sorted array to search. Instead the answer itself is a number in a range, you cannot compute it directly — but given a candidate you can check it cheaply. Line the candidates up smallest to largest and their verdicts are sorted even though nothing else is:

candidate capacity: 10 11 12 13 14 15 16 17 ... 55 works in 5 days? F F F F F T T T ... T ^ the boundary -- this is the answer Once a capacity works, every larger capacity works too. That monotonic F...F T...T strip is the "sorted array" you binary search.

Three questions before you write a line

  1. What is the answer? A capacity, a speed, a largest-part sum — a single number, not an index.
  2. What is the feasibility check, and is it monotonic? Write is_feasible(value) as a plain greedy scan. If a larger value can ever be worse, binary search is off the table.
  3. Which bounds bracket it? Pick a lo that obviously fails (or is the smallest legal value) and a hi that obviously works. Sloppy bounds are the number-one bug here, not the loop.

T3+The skeleton

smallest_feasible.pypython
def smallest_feasible(low, high, is_feasible):
    """Smallest value in [low, high] where is_feasible(value) is True.

    Requires monotonic feasibility: once a value works, every larger
    value works too --  F F F F T T T T  -- and we want that boundary.
    """
    while low < high:
        middle = low + (high - low) // 2

        if is_feasible(middle):
            high = middle        # middle might BE the answer, so keep it
        else:
            low = middle + 1     # middle fails, and so does everything below it

    return low                   # low == high == the boundary

This is Template 2 with is_feasible(middle) in place of nums[mid] >= target. For a maximize problem ("largest value that still works") the strip is T T T F F F: use middle = low + (high - low + 1) // 2, then low = middle on success and high = middle - 1 on failure. The + 1 rounds mid upward and is what stops the infinite loop.

P6Capacity To Ship Packages — LC 1011

Packages must ship in their given order. Guess a truck capacity; the greedy packer then tells you how many days that capacity costs. Bigger truck, never more days — the monotonicity we need.

ship_within_days.py — LC 1011python
def ship_within_days(weights, days):
    def days_needed(capacity):
        """Load packages in order; start a new day when the truck would overflow."""
        days_used = 1
        current_load = 0

        for weight in weights:
            if current_load + weight > capacity:
                days_used += 1        # this package begins a new day
                current_load = 0
            current_load += weight

        return days_used

    # The truck must at least hold the single heaviest package, and it never
    # needs to be bigger than "everything in one day".
    low = max(weights)
    high = sum(weights)

    while low < high:
        middle = low + (high - low) // 2

        if days_needed(middle) <= days:
            high = middle             # this capacity is enough, try smaller
        else:
            low = middle + 1          # too small, the packages spill over

    return low
1 / 7walkthrough — binary search on the answer (LC 1011)
1
2
3
4
5
6
7
8
9
10
days allowed 5
lo 10
hi 55
Ship these ten packages in their given order within 5 days — find the smallest truck capacity that manages it. The truck must hold the heaviest package, so lo = 10; loading everything at once always works, so hi = 55. From here on, each cell shows the day that package ships on.
Same problem, three costumes
LC 875 Koko guesses an eating speed and counts hours. LC 1011 guesses a capacity and counts days. LC 410 Split Array Largest Sum guesses a largest-allowed part and counts subarrays — it is LC 1011 with "days" renamed to "splits". Recognise one and you have all three.
Mistake 6 — bounds that exclude the answer
Starting low = 1 in LC 1011 is not wrong (the greedy just reports a huge day count), but starting low = 0 divides by zero in Koko, and starting high = max(weights) excludes every valid answer. Sanity-check that is_feasible(high) is True and is_feasible(low - 1) would be False.
Mistake 7 — a feasibility check that is not monotonic
"Smallest k such that some property holds" only binary-searches if the property, once true, stays true forever. If a bigger k can break it, you need a different technique — binary search will happily return a wrong boundary without complaining.
Mistake 8 — counting the feasibility check as free
Each probe runs a full O(n) scan, so the total is O(n log(range)), not O(log n). That is still fast, but say it out loud in an interview.
10 practice

Practice ladder

In this order — easiest first. Tick each one as you solve it, and re-solve anything that took more than 25 minutes two days later.

14 problems
easyLC 704
Binary Search
Template 1, straight from memory. The baseline.
easyLC 35
Search Insert Position
Template 2 — lower bound is the insert position.
easyLC 278
First Bad Version
Template 2 over a boolean API - find the first index where isBadVersion is True.
mediumLC 74
Search a 2D Matrix
Treat the matrix as one flat sorted array: row = idx // cols, col = idx % cols.
mediumLC 34
First and Last Position
Template 2 twice: lower bound + upper bound.
mediumLC 33
Search in Rotated Sorted Array
Template 1 + identify which half is sorted.
mediumLC 153
Find Minimum in Rotated Sorted Array
Template 2 — compare mid vs right.
mediumLC 852
Peak Index in a Mountain Array
Template 2 on the predicate nums[mid] > nums[mid + 1] - the guaranteed-single-peak version of LC 162.
mediumLC 162
Find Peak Element
Template 2 on an unsorted array — climb toward the rise.
mediumLC 981
Time Based Key-Value Store
Per-key append-only list of (timestamp, value) - upper bound, then step back one.
mediumLC 875
Koko Eating Bananas
Template 3 — binary search the answer + feasibility check.
mediumLC 1011
Capacity To Ship Packages Within D Days
Template 3 - guess a capacity, greedily count days, shrink the range.
hardLC 410
Split Array Largest Sum
Identical to LC 1011 with subarrays instead of days - minimize the maximum part.
hardLC 4
Median of Two Sorted Arrays
The boss fight: Template 2 partition binary search.