sqrt_binary2.java

public int mySqrt(int x) {
    	long left = 0, right = x/2 +1;
    	long ans = 0;
    	while(left <= right){
    	    long mid = (left + right) / 2;
    	    if(mid * mid <= x){
    	        ans = mid;
    	        left = mid + 1;
    	    } else {
    	        right = mid - 1;
    	    }
    	}
        return (int)ans;
    }
//对于一个非负数n,它的平方根不会大于(n/2+1)在[0, n/2+1]这个范围内可以进行二分搜索,求出n的平方根.