Easy
注意几点，overflow所以全部设成long, 返回的时候cast一下。
还有binary search的时候始终拿midmid跟x比较，不是跟end比较。
最后return的时候先看endend <= x不

class Solution {
    public int mySqrt(int x) {
        if (x == 0){
            return 0;
        }
        //9
        //start=1
        //end=5
        //mid=3
        long start = 1;
        long end = x;
        while (start + 1 < end){
            long mid = start + (end - start) / 2;
            if (mid*mid == x){
                return (int) mid;
            } else if (mid*mid > x){
                end = mid;
            } else {
                start = mid;
            }
        }
        if (end*end <= x){
            return (int) end;
        } else {
            return (int) start;
        }
    }
}