Binary Search on Answers
Searching for a number.
Binary search isn't only for lists. If you can ask, is this answer too small or too big, you can binary search the answer itself. Let's find the square root of a number, without using any maths library.

- Not only for lists
- Too small, or too big?
- Search the answer itself
Integer square root
We want the biggest whole number whose square is at most N. The answer is somewhere between zero and N. We guess the middle. If its square is too big, the answer is lower. Otherwise, it might be the answer, so we remember it, and try higher. Run it. The square root of two million is one thousand four hundred and fourteen, found in about twenty guesses.
def int_sqrt(n):
low, high, best = 0, n, 0
while low <= high:
mid = (low + high) // 2
if mid * mid > n:
high = mid - 1
else:
best = mid
low = mid + 1
return best
for n in [16, 50, 2_000_000]:
print(n, "->", int_sqrt(n))16 -> 4 50 -> 7 2000000 -> 1414
When to try this
Look for problems that ask for the smallest or largest value that works, where checking a guess is easy. The smallest speed to finish on time. The largest box size that fits. If a bigger guess is always at least as good, or always worse, binary search the answer.
| key | value |
|---|---|
| Ask | is this guess too big? |
| Range | low and high answers |
| Checks | about log n |
| Examples | speeds, sizes, limits |
Summary
If you can say too big or too small, you can binary search the answer. Next, a new section. Sorting algorithms.
Key takeaways- Guess the middle
- Too big? Go lower
- O(log n) guesses