Sqrt(x)
Compute the integer square root of x.
Pattern fit
This is a clean answer-space binary search because you are looking for the largest mid such that mid^2 <= x.
Key observation
You are not searching array positions; you are searching the feasible numeric answer boundary.
Target complexity
O(log x) / O(1)
How to break down the solution cleanly
This is a clean answer-space binary search because you are looking for the largest mid such that mid^2 <= x.
You are not searching array positions; you are searching the feasible numeric answer boundary.
Write the monotonic predicate in plain English first.
Choose a search interval that definitely contains the answer.
Reference implementation
Python# Generic pattern template
# Find first position where check(mid) is true
left, right = 0, n
while left < right:
mid = left + (right - left) // 2
if check(mid):
right = mid
else:
left = mid + 1
return left
Common pitfalls
Overflowing when computing mid * mid.
Returning the wrong boundary when x is not a perfect square.
Common follow-ups
How would you avoid overflow cleanly?
Can you phrase this as first false / last true?
Continue with related problems
Build repeatable depth inside the Binary Search cluster before moving on.