Binary search

No. 05 · SVG · Calipers on a rulesearch an array · search a range · min_valid

Drag across the rule. Click it, then use ← → to step and Space to play.

Check the middle, throw away the half that can't hold the answer. On sorted data, one look at the middle element tells you which half the answer is in, so the other half drops out of the search. Every check halves what is left: 16 candidates need at most 5 checks, a million need 20. The same idea works on a range of possible answers, keeping the smallest one that works.

FIG. 5 · Sorted values set in a type case on an engraved rule. A caliper grips the part that can still hold the answer: its two jaws are the pointers L and R (lo and hi when searching a range). Each check reads the tile under the red mid needle, and one jaw closes past it. Everything outside the jaws is hatched out but stays on the rule, so you can watch the window shrink. Callouts: A L jaw, B R jaw, C mid, D thrown away; in a search range also E res, the best answer so far, and for Koko F the piles.

Step 1 / 1
READY
Checks
Candidates left
Most checks needed
Result
Codebinary_search
def binary_search(nums, target):
    L, R = 0, len(nums) - 1
    while L <= R:
        mid = (L + R) // 2
        if nums[mid] < target:
            L = mid + 1
        elif nums[mid] > target:
            R = mid - 1
        else:
            return mid
    return -1

Examples

Search range · LeetCode 875

Piles [3, 6, 7, 11], 8 hours. Find the smallest eating speed k that finishes in time. Faster always works if slower works, so binary search the speeds 1..11. Trigger: "minimum speed such that…".

O(n log m) timeO(1) spacelog m speeds tried (m = biggest pile), each checked against all n piles
Search range · LeetCode 278

Versions 1..10; once a version is bad, every later one is bad. Find the first bad one with as few isBadVersion() calls as possible. Trigger: "first", "earliest", "smallest such that".

O(log n) timeO(1) spaceeach call halves the versions still in question

Time and space: why halving is so fast

SearchTimeSpaceWhyLast run on the bench
Linear scanO(n)O(1)Checks elements one by one. Works on unsorted data.for comparison
Binary search on a sorted arrayO(log n)O(1)Each check halves the candidates; only L, R and mid are stored.not run yet
Binary search on a range of answersO(log(range) × check)O(1)log(range) guesses, and each guess runs works() once. For Koko, works() costs O(n), so O(n log m).not run yet

How many checks binary search needs

nLinear scan, worst caseBinary search, worst case

The one requirement: a yes/no line

Binary search only works when one side of the middle can be ruled out. In a sorted array, everything left of a smaller value is smaller too. In a search range, works() must be monotonic: once it is True, it stays True for every bigger value (if Koko finishes at speed 4, she also finishes at 5). The range looks like ✗ ✗ ✗ ✓ ✓ ✓, and binary search finds the first ✓.

How to remember it

Binary search: check the middle, keep the half that can hold the target"Look at the middle element. If the target is bigger, search the right half. If it's smaller, search the left half. Repeat until you find it or run out of elements."
Search range: guess, test, keep the smallest that worksGuess the middle value. If it works, save it and try smaller; if not, go bigger. When the range is empty, the saved value is the answer.

Trigger words: when the problem wants binary search

Search the array

  • sorted array
  • find the target in O(log n)

The data is already in order, so half of it can be ruled out with one comparison.

Search the answer range

  • minimum speed such that…
  • minimum capacity
  • minimum days
  • Koko Eating Bananas

You can check whether one candidate answer works, and bigger answers keep working.

Template

def binary_search(nums, target):
    L, R = 0, len(nums) - 1
    while L <= R:
        mid = (L + R) // 2
        if nums[mid] < target:
            L = mid + 1
        elif nums[mid] > target:
            R = mid - 1
        else:
            return mid
    return -1

def min_valid(lo, hi, works):      # smallest value where works() is True
    res = hi
    while lo <= hi:
        mid = (lo + hi) // 2
        if works(mid):
            res = mid              # save it
            hi = mid - 1           # try smaller
        else:
            lo = mid + 1
    return res