Sqrt(x)
Compute the integer square root of x without a built-in by binary searching for the largest k whose square is at most x.
Problem Understanding
Sqrt(x): given a non-negative integer x, return the square root of x rounded down to the nearest integer, without using a built-in power or square-root function.
Example: x = 8 returns 2, because √8 ≈ 2.83.
The Intuition: Search the Answer, Not an Array
There is no array here, but binary search still applies because the answer space is ordered. For each candidate k, ask: does k² ≤ x? The answers look like yes, yes, …, yes, no, no, …, and the last yes is ⌊√x⌋.
- Search
kin[0, x]. - If
mid² ≤ x,midis a valid answer, but a bigger one may exist: record it and go right. - Otherwise
midis too big: go left.
This "last true" search is the same shape as Search Insert Position, and searching over answers rather than indexes is the idea behind Koko Eating Bananas. The exact-match version, which only asks whether some k squares to x, is Valid Perfect Square.
Interactive Walkthrough
Every candidate k from 0 to x is shown with k² underneath. The range [lo, hi] still in play is tinted, mid is filled, and the best k so far turns green. Try Just below, where x = 24 sits one short of a perfect square.
Dry Run Table
Input: x = 8
| lo | hi | mid | mid² | Action | ans |
|---|---|---|---|---|---|
| 0 | 8 | 4 | 16 | > 8: hi = 3 | 0 |
| 0 | 3 | 1 | 1 | ≤ 8: lo = 2 | 1 |
| 2 | 3 | 2 | 4 | ≤ 8: lo = 3 | 2 |
| 3 | 3 | 3 | 9 | > 8: hi = 2 | 2 |
Answer: 2.
The Solution Template
Binary search for the last k with k² ≤ x. Java, C++ and C use 64-bit integers so mid * mid cannot overflow.
Sqrt(x) Code
1var mySqrt = function(x) {2 let lo = 0, hi = x, ans = 0;3 while (lo <= hi) {4 const mid = Math.floor((lo + hi) / 2);5 if (mid * mid <= x) {6 ans = mid;7 lo = mid + 1;8 } else {9 hi = mid - 1;10 }11 }12 return ans;13};
Edge Cases & Common Mistakes
- x = 0 or 1: the answer is x itself; the loop handles both without special cases.
- Overflow: with 32-bit ints,
mid * midoverflows near x = 2³¹ − 1. Use 64-bit math or comparemid <= x / mid. - Returning lo instead of ans: after the loop,
hi(notlo) equals ⌊√x⌋; keepingansavoids the confusion. - Perfect squares:
x = 4must return 2, so test with≤, not<. - Using floating point:
int(x ** 0.5)can be off by one for large x because of rounding; integer search is exact.
Summary
Binary search k over [0, x] for the last value with k² ≤ x: record mid and go right when it fits, go left when it overshoots. Use 64-bit math for the square. O(log x) time and O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet