Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1:
Input: 4
Output: 2
Example 2:
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
the decimal part is truncated, 2 is returned.
// Binary Search
int mySqrt(int x) { // time: O(log(n)); space: O(1)
if (x <= 1) return x;
int l = 0, r = x;
while(l < r) {
int mid = l + (r - l) / 2;
if (mid <= x / mid) l = mid + 1;
else r = mid;
}
return r - 1;
}
// Newton's Method
// Xi+1 = Xi + (n / Xi) / 2
int mySqrt(int x) {
if (x <= 1) return x;
int r = x / 2;
while (r > x / r) {
r = (r + x / r) / 2;
}
return r;
}