Sqrt(x)

sqrt.java

/*
Implement int sqrt(int x).
Compute and return the square root of x.
Algorithm:
1. binary search
2. make sure the right < sqrt(Integer.MAX_VALUE)
*/
public class Solution {
    public int sqrt(int x) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int left = 0; 
        int right = x/2+1 < Math.sqrt(Integer.MAX_VALUE) ? x/2+1 : (int)Math.sqrt(Integer.MAX_VALUE);;
        if(x == 1) return 1;
        int mid = 0;
        while(right >= left) {
            mid = (right + left) / 2;
            int sq = mid * mid;
            if(sq == x) {
                return mid;
            } else if(sq > x) {
                right = mid - 1;
            } else if(sq < x) {
                left = mid + 1;
            }
        }
        if(mid * mid > x) return mid-1;
        else return mid;
    }
}