AI Hints
Home›DSA in Python Tutorial›Binary Search
DSA in Python · Lesson 48 of 132

Binary Search on Answers

Searching for a number.

⏱ 2 min read▶ Video at 55:41🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Binary Search on Answers
From the video: Binary Search on Answers
  • 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.

sqrt.pypython
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))
Output
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.

keyvalue
Askis this guess too big?
Rangelow and high answers
Checksabout log n
Examplesspeeds, 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
Next up: Why Sorting Matters — order makes everything easier