sqrt

二分法，注意考虑溢出

class Solution {
public:
    /**
     *
     * @param x int整型
     * @return int整型
     */
    int sqrt(int x) {
        // write code here
        // 需要考虑溢出
        if (x <= 0) return 0;
        int left = 1, right = x;
        while (left < right) {
            long middle = (left + right) / 2;
            if (middle * middle <= x && (middle + 1) * (middle + 1) > x) return middle;
            if (middle * middle > x)  right = middle;
            else left = middle;
        }
        return left;
    }
};