69. Sqrt(x)

Implement int sqrt(int x).

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

public int mySqrt(int n) {
    int l = 0, r = n;
    while(l + 1 < r) {
        int mid = l + (r-l) / 2;
        long square = (long)mid * mid;
        if(square == n) return mid;
        else if(square < n) l = mid;
        else r = mid;
    }
    return (long)r * r <= n ? r : l;
}
  • Optimized Brutal Force: Reduce search Space
public int mySqrt(int n) {
    long x = n;
    long y = x;
    while(x/2 * x/2 > y) {
        x /= 2;
    }
    for(long i = x / 2; i <= x; i++) {
        long j = i * i;
        if(j == y) return (int)i;
        else if(j > y) return (int)i-1;
    }
    return -1;
}