Integer Square Root

Given a non-negative integer x, return the greatest integer r such that r * r <= x. In other words, return the square root of x rounded down to the nearest…

Given a non-negative integer `x`, return the greatest integer `r` such that `r * r <= x`. In other words, return the square root of `x` rounded down to the nearest integer. Do not use a built-in exponent or square-root function.

- `0 <= x <= 10^9` - Return only the integer floor of the square root.

Example 1: input x = 8; output 2. The square root lies between 2 and 3, so rounding down gives 2.

Example 2: input x = 16; output 4. 4 × 4 equals 16 exactly.

Example 3: input x = 0; output 0. Zero is its own square root.

Category: Binary Search. Topic: binary-search. Difficulty: Easy. Patterns: binary-search-on-answer.