93. Sqrt(x)

Easy · Binary Search

Given a non-negative integer x, return the integer square root of x (i.e., the greatest integer whose square is less than or equal to x). Do not use any built-in exponentiation operator or function.

For example, the integer square root of 8 is 2 because 2² = 4 ≤ 8 and 3² = 9 > 8.

Examples

Example 1
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, and 2² = 4.
Example 2
Input: x = 8
Output: 2
Explanation: The square root of 8 is approximately 2.83, but we return the integer part, which is 2. Note that 2² = 4 ≤ 8 and 3² = 9 > 8.

Constraints