Sqrt(x)
Implement int sqrt(int x). Compute and return the square root of x. x is guaranteed to be a non-negative integer.
Example 1: Input: 4 Output: 2
Example 2: Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.
Solution: Binary Search
When comparing root with target, we need to prevent overflow.
int mySqrt(int x) {
if (x <= 1) return x;
int left = 1, right = x/2, mid = 0;
while (left <= right) {
mid = left + (right - left)/2;
if (x / mid == mid) return mid;
else if (mid < x / mid) left = mid + 1;
else right = mid - 1;
}
return right;
}