69 Sqrt(x)

Implementint sqrt(int x).

Compute and return the square root ofx.

xis 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) Using a binary search. Also we have to consider overflow case.

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        int l = 1;
        int r = x;
        int result = 0;
        while (l <= r) {
            int m = (l+r)/2;
            if (m == x/m) return m; // we have to use x/m instead of m*m to avoid overflow
            else if (m <= x/m) {
                l = m+1;
                result = m;
            } else r = m-1;
        }
        return result;
    }
}