easyBinary SearchPure DSA~14 min
Integer Square Root
A sizing helper needs the largest integer whose square does not exceed a capacity value — the floor of its square root — computed without floating-point math.
Problem
Given a non-negative integer x, return the floor of its square root (the largest integer r with r·r ≤ x). Do not use any built-in sqrt function.
Input
An integer x (0 ≤ x ≤ 2^31 − 1).
Output
An integer — floor(sqrt(x)).
Constraints
- No built-in square-root function
- Answer is the integer floor
- Beware overflow when squaring the midpoint
Examples
Example 1
Input
x = 8
Output
2
sqrt(8) ≈ 2.828; the floor is 2.
Example 2
Input
x = 16
Output
4
16 is a perfect square.