public int sqrt_v2(int x) {
        // write your code here
        long begin = 0, end = x;
        while (begin + 1 < end) {
            long mid = begin + (end - begin) / 2;
            if (x == mid * mid)
                return (int) mid;
            else if (x < mid * mid) {
                end = mid;
            } else {
                begin = mid;
            }
        }
        if (x < end * end)
            return (int) begin;
        else
            return (int) end;
    }