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;
}