Given a non-negative integer x, return the square root of x rounded down to the nearest integer.
Example 1:
Input: x = 4
Output: 2
Example 2:
Input: x = 8
Output: 2
Explanation: sqrt(8) = 2.828..., rounded down = 2
Binary search on the range [0, x] to find the largest integer whose square ≤ x.
1class Solution {
2 public int mySqrt(int x) {
3 if (x < 2) return x;
4
5 int left = 0, right = x;
6 while (left <= right) {
7 int mid = left + (right - left) / 2;
8 long square = (long)mid * mid;
9
10 if (square == x) return mid;
11 else if (square < x) left = mid + 1;
12 else right = mid - 1;
13 }
14 return right;
15 }
16}