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.

tag: binary search

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        //if (x == 1) return 1;

        long left = 1, right = x;
        while (left + 1 < right){
            long mid = left + (right - left) / 2;

            if (mid * mid  == x){
                return (int)mid;
            }
            else if (mid * mid < x){
                left = mid;
            }
            else{
                right = mid;
            }
        }

        if (right * right <= x){
            return right >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)right;
        }

        return left >= Integer.MAX_VALUE ? Integer.MAX_VALUE : (int)left;
    }
}