Easy Binary Search Binary Search
In plain English: Find the largest integer whose square is less than or equal to x.
Binary search on the answer space [0, x]: if mid*mid <= x, the answer is at least mid; if mid*mid > x, it is less than mid.
Prompt
Given a non-negative integer x, compute floor(sqrt(x)) without using math.sqrt.
Try to write it from scratch before scrolling down.
Solution
def my_sqrt(x):
if x < 2:
return x
lo, hi = 1, x // 2
while lo <= hi:
mid = (lo + hi) // 2
sq = mid * mid
if sq == x:
return mid
elif sq < x:
lo = mid + 1 # answer might be larger
else:
hi = mid - 1 # answer must be smaller
return hi # hi is floor(sqrt(x))
# Test: my_sqrt(8) == 2
# Test: my_sqrt(16) == 4
# Test: my_sqrt(0) == 0