pattern heroPT–23LeetCode Extension

Binary search

Look at the middle and decide which half holds the answer; throw the other half away. Each step halves what is left, so even a million items take about twenty steps.

Variant
P05 Binary searchFind a number · 1×

Example problem: find the index of 12 in the sorted array [2, 5, 8, 12, 16, 23, 38, 56, 72].

021528312416523638756872lo
still in the rangemiddle, checked nowthrown awayfound

lo starts at the first index, 0

lo = 0hi = –mid = –
01/21
restart · back · play · step
Speed
1function binarySearch(nums, target):
2 lo = 0
3 hi = len(nums) - 1
4 while lo <= hi: // ends if not found
5 mid = floor((lo + hi) / 2)
6 if nums[mid] < target:
7 lo = mid + 1
8 else if nums[mid] > target:
9 hi = mid - 1
10 else:
11 return mid

← → step · space play/pause

How to recognise

a sorted array, O(log n) in the constraints, or "the smallest value that works" when every bigger value works too.

How to solve problems like this

  1. Set lo and hi to the ends of the range where the answer can be.
  2. Look at the middle and ask a yes-or-no question about it.
  3. Keep the half that can still hold the answer. Move lo or hi past mid, so the range always shrinks.
  4. Stop when you find it. If lo passes hi, the answer is not there.

Variant: Search the answer

The same, but search for the answer itself, such as the lowest speed, not for an item in an array. It works when any guess is easy to check and the checks go "no, no, …, yes, yes": the border between no and yes is the answer.

  1. Spot it: the task asks for "the minimum x such that ..." (or the maximum), and checking one given x is easy.
  2. Find the bounds: lo is the smallest x that could work, hi is a value that surely works, like the largest pile here.
  3. Write feasible(x), a yes-or-no check, and make sure it is monotonic: once it says yes, it says yes for every bigger x.
  4. Loop while lo < hi: if feasible(mid), set hi = mid so mid stays in the range, else set lo = mid + 1. When they meet, lo is the left-most feasible value.

Variant: Rotated array

The same, but the array is rotated, as if it were cut and its pieces swapped. Cut it in the middle and one half is still sorted, which tells you where to go next.

  1. Spot it: the array is "sorted, but rotated", or it rises and then falls, and you still need O(log n).
  2. At each mid, find the half you can trust: compare nums[lo] with nums[mid] to see which half is sorted.
  3. Check whether the target lies between the ends of the sorted half. Keep that half if it does, the other half if not.
  4. To find the minimum of a rotated array, compare nums[mid] with nums[hi]: if nums[mid] > nums[hi], the drop and the minimum are to the right of mid, else at mid or to its left.
  5. To find a peak, compare nums[mid] with its neighbour nums[mid + 1]: if the next one is bigger, a peak is to the right, else at mid or to the left.

Where it's used

  • git bisect. It finds the commit that broke something. It picks the commit halfway between "still worked" and "already broken", you test it, and half of the history is dropped. Even among 1,000 commits the culprit is found in about 10 tests.
  • Database indexes. Inside each page of an index the keys are kept in order, and PostgreSQL finds the one it needs by halving, not by reading them all.
  • Python. The bisect module finds where to insert a number into a sorted list so that it stays sorted.