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.
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
def works(x): # smallest x with x * x >= target
return x * x >= target
def minEatingSpeed(piles, h): # LeetCode 875
def works(k): # can Koko finish at speed k?
hours = sum((p + k - 1) // k for p in piles) # ceil(p / k) per pile
return hours <= h
return min_valid(1, max(piles), works)
def firstBadVersion(n): # LeetCode 278
def works(v): # is version v bad?
return isBadVersion(v) # every version after the first bad one is bad too
return min_valid(1, n, works)
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…".
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".
| Search | Time | Space | Why | Last run on the bench |
|---|---|---|---|---|
| Linear scan | O(n) | O(1) | Checks elements one by one. Works on unsorted data. | for comparison |
| Binary search on a sorted array | O(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 answers | O(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 |
| n | Linear scan, worst case | Binary search, worst case |
|---|
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 ✓.
The data is already in order, so half of it can be ruled out with one comparison.
You can check whether one candidate answer works, and bigger answers keep working.
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