Patternwise

Binary Search

Halve the search space every step — on arrays or answers.

Brute force
O(n) — scan every candidate (or O(n · range) for answer-search)
With the pattern
O(log n) probes — O(n log range) when each probe costs O(n)
Extra space
O(1)

In plain English

“Guessing a number between 1 and 1,000 where your friend only says "higher" or "lower": you always guess the middle, so ten guesses are enough. The trick works on anything where a yes/no answer flips exactly once, like finding the slowest walking pace that still gets you home before dark.”

Why it's fast

Brute force checks every candidate one by one. If a yes/no question is monotonic — all False then all True — one probe at the middle rules out half the candidates, giving O(log n) probes. The candidates don't have to be array indices: they can be speeds, capacities or days (binary search on the answer).

Spot it when the problem says…

  • sorted array / rotated sorted array
  • find the first / last position of
  • minimum capacity / speed / time such that…
  • O(log n) required
  • maximize the minimum (or minimize the maximum)
  • find a peak / boundary

Visualize

Binary search in a sorted array

Return the index of target in a sorted array, or -1 if it isn't there.

0
2
↑lo
1
5
2
8
3
12
4
16
5
23
6
38
7
56
8
72
9
91
↑hi
01/09

Search space is the whole array: 10 candidates.

pythonline 2
1def search(nums, target):2    lo, hi = 0, len(nums) - 13    while lo <= hi:4        mid = (lo + hi) // 25        if nums[mid] == target:6            return mid7        if nums[mid] < target:8            lo = mid + 1     # answer is right of mid9        else:10            hi = mid - 1     # answer is left of mid11    return -1

variables

lo
0
hi
9
target
23

How to apply it

  1. 01Define a predicate ok(x) that is False…False, True…True over the search range.
  2. 02Set lo and hi to bound the answer (inclusive or half-open — pick one and stick to it).
  3. 03Loop: mid = (lo + hi) // 2; if ok(mid) shrink to the left half (keep mid), else move right past mid.
  4. 04When the loop ends, lo is the first True — check it's in range before returning.

Variations you'll meet

Classic exact match

The visualizer's example: find target in a sorted array, closed interval [lo, hi].

python
def search(nums: list[int], target: int) -> int:    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

First True / lower bound template

The one template to memorize. Half-open [lo, hi); returns the first index where ok is True (or hi if none). Same as bisect_left when ok = nums[i] >= target.

python
def first_true(lo: int, hi: int, ok) -> int:    # smallest x in [lo, hi) with ok(x) True; hi if none    while lo < hi:        mid = (lo + hi) // 2        if ok(mid):            hi = mid          # mid might be the answer        else:            lo = mid + 1      # mid is definitely not    return lodef lower_bound(nums: list[int], target: int) -> int:    return first_true(0, len(nums), lambda i: nums[i] >= target)

Binary search on the answer (Koko)

Search the speed, not the array. ok(speed) = can she finish within h hours? Faster always works if slower works, so it's monotonic.

python
def min_eating_speed(piles: list[int], h: int) -> int:    def ok(speed: int) -> bool:        hours = sum((p + speed - 1) // speed for p in piles)        return hours <= h    lo, hi = 1, max(piles)    while lo < hi:        mid = (lo + hi) // 2        if ok(mid):            hi = mid        else:            lo = mid + 1    return lo

Rotated sorted array

At least one half around mid is sorted; check whether the target lies in that sorted half to decide which way to go.

Common mistakes

  • Mixing templates: while lo < hi with hi = mid - 1 skips the answer; while lo <= hi with hi = mid loops forever.
  • Setting the answer range wrong for search-on-answer (e.g. lo = 0 causes division by zero in Koko).
  • Using a non-monotonic predicate — binary search silently returns garbage.
  • Computing hours with float division instead of ceiling integer division (p + s - 1) // s.
  • Not checking the returned index is in bounds and actually equals target for lower-bound searches.

Practice ladder

Easy → hard. Tick them off as you go.

0/8 solved
  1. 01Binary Search ↗Easy
  2. 02Search Insert Position ↗Easy
  3. 03First Bad Version ↗Easy
  4. 04Find First and Last Position of Element in Sorted Array ↗Medium
  5. 05Search in Rotated Sorted Array ↗Medium
  6. 06Koko Eating Bananas ↗Medium
  7. 07Capacity To Ship Packages Within D Days ↗Medium
  8. 08Median of Two Sorted Arrays ↗Hard

Think you've got it?

Let the AI interviewer throw a Binary Search problem at you and grade how you explain it.

Mock interview