Binary Search · LC #69
Sqrt(x)
Given a non-negative integer `x`, return the integer part of its square root (floor), computed without using built-in exponent functions, using binary search on the answer space.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given a non-negative integer `x`, return the square root of `x` rounded down to the nearest integer. The returned integer should be non-negative as well. You must not use any built-in exponent function or operator, such as `pow(x, 0.5)` or `x ** 0.5`.
Sample I/O
Input: x = 4 Output: 2 Input: x = 8 Output: 2 (sqrt(8) ≈ 2.828, floor = 2)
Time: O(log x) · Space: O(1)
Intuition
How to Think About It
Intuition
The function f(m) = m² is monotonically increasing, so we can binary-search the answer space [0, x] to find the largest m where m² ≤ x - the classic "binary search on value" pattern applied to a mathematical predicate.
Core Concept
Set `l=0`, `r=x`. For each `mid`, compute `mid*mid`. If equal to x return mid; if less than x shrink left boundary upward; if greater shrink right boundary down. After the loop, `r` holds the largest integer whose square does not exceed x.
When to use
Any problem asking for a floor/ceiling of an implicit function over a monotone domain where evaluating the predicate is O(1) or O(n) and a direct formula does not exist.
When NOT to use
When x fits in a float range and precision is acceptable - `Math.floor(Math.sqrt(x))` is simpler; avoid the manual approach then.
Key Insights
What to Know Cold
- Search range upper bound can be reduced to `x/2` for x ≥ 2 since sqrt(x) ≤ x/2 when x ≥ 4.
- Use `long` in Java/C++ when computing `mid*mid` - mid can be up to 2^31-1, squaring overflows int.
- At loop exit `r` is the floor answer; `l` is `r+1` (the ceiling starting point).
- Special-case x=0 and x=1 to avoid edge issues with the `x/2` upper bound optimization.
- This is the canonical example of "binary search on value/answer" - the predicate here is `m*m <= x`.
3 examples
Worked Examples
Perfect square
x=4, expected output 2.
l=0,r=4. mid=2 → 4==4 → return 2.
function mySqrt(x: number): number {
let l=0, r=x;
while(l<=r){
const m=Math.floor((l+r)/2);
if(m*m===x) return m;
else if(m*m<x) l=m+1;
else r=m-1;
}
return r;
}Output: 2
Exact hit path - validates early return on perfect square.
Non-perfect square - floor required
x=8, expected output 2.
Loop exit: l=3,r=2. r=2 because 2*2=4<8 and 3*3=9>8. Return r=2.
Output: 2
Core case; shows why we return `r` (last valid integer) not `l`.
x=0 edge case
x=0.
l=0,r=0. mid=0. 0*0==0 → return 0.
Output: 0
Edge case: zero input; algorithm must handle without divide-by-zero.