平方根

//关键在与int整性的平方会溢出，需要用long型，如果用long型不够，可以使用BigInteger或者使用大数乘法等。

public static int sqrt (int x) {
        // write code here
        if(x<=0) return 0;
        long left = 1;
        long right = x;
        //找出最后一个数平方小于等于x
        while(left+1<right){
            long mid = (right-left)/2+left;
            if(mid*mid==x) {
                return (int)mid;
            }
            else if(mid*mid < x) left = mid;
            else right = mid-1;
        }
        if(x>=right*right) return (int)right;
        else if(x>=left*left) return (int)left;
        else return -1;//找不到
    }