Binary Search

Li Chen

Sep. 13th 2023

15-195/295

Outline

• Binary Search
• Binary Search the Answer
• Ternary Search

Binary Search

• Locate x in a sorted sequence
• Linear Search: O(n)-time
• Binary Search: O(log n)-time
• n = 10^6, log n ≈ 20

Binary Search: How?

• Task: Locate the first “1” in sequence x = 0, 0, …, 0, 1, 1, …, 1
• Possible Range: L = 0, R = n - 1 (0-based)
• Access x[i] between L and R
• If x[i] = 0
• Try again with refined range [i + 1, R]�

No “1” in between L and i

Binary Search: How?

• Task: Locate the first “1” in sequence x = 0, 0, …, 0, 1, 1, …, 1
• Possible Range: L = 0, R = n - 1 (0-based)
• Access x[i] between L and R
• If x[i] = 1
• Keep i and move on to range [L, i - 1]

First “1” in between L and i

i through R are all “1”s

Binary Search: How?

• Want to get rid of most things in both cases
• Pick the middle one! Set i = (L + R) / 2
• Whatever x[i] is, we reduce the range by half

Binary Search: How?

• Possible range [L, R]
• Check x[mid]
• If 0, no “1” in [L, mid]
• If 1, either mid or�somewhere in [L, mid - 1]
• Repeat

Binary Search: How?

Binary Search on Answer

• Task: Locate the first “1” in sequence x = 0, 0, …, 0, 1, 1, …, 1
• We don’t even need to store x
• All we need: can compute x[mid]�

Find square root

• Task: Given y, find smallest x such that x * x ≥ y
• a[1], a[2], …, where a[x] = 1 if x * x ≥ y
• a = 0, 0, …, 1, 1, …
• Equivalent: Locate first 1 in a[]
• y can be large as 10^18
• No memory to write down a[]

Find square root

• We know a[x] given x
• If x * x ≥ y, a[x] = 1
• Otherwise, a[x] = 0
• Can compute a[mid] very fast

Find square root

Ternary Search

• Maximize “unimodal” function y = f(x)

Ternary Search

• Maximize “unimodal” function y = f(x)
• Possible range�[x0, x3]
• max in�[x1, x3]

x0

x3

x1

x2

y = f(x)

f(x1) < f(x2)

Ternary Search

• Maximize “unimodal” function y = f(x)
• Possible range�[x0, x3]
• max in�[x0, x2]

x0

x3

x1

x2

y = f(x)

f(x1) > f(x2)

Ternary Search

• Maximize “unimodal” function y = f(x)
• Possible range�[x0, x3]
• Pick x1, x2�divide [x0, x3]

x0

x3

x1

x2

y = f(x)

Ternary Search

• Maximize y = x * (1 - x)
• Up to small error
• Do more iterations

2nd thought

• Binary Search also works
• Derivative:�> 0, > 0, …, = 0, < 0, < 0, …
• Binary Search the first point of non-positive derivative
• Closed form: f’(x)
• Numerical: (f(x + eps) - f(x)) / eps, eps -> 0

Summary

• Binary Search
• Locate first 1 in sequence 00…011…
• O(log n) queries
• Binary Search on Answer
• Don’t need to write down the whole sequence
• Reduce optimize to verification, i.e., check a[x] is 1 or not
• Ternary Search
• Find max in unimodal function
• Work on real numbers: more iterations to get small error