本题很简单，二分法，用二分法模板即可。 需非常注意，mid*mid可能会很大导致溢出，所以要用long型而非int型。
class Solution { public: /** * @param x: An integer * @return: The sqrt of x */ int sqrt(int x) { long start = 0; long end = x; while (start + 1 < end) { long mid = start + (end -start) / 2; if (mid * mid > x) { end = mid; } else { start = mid; } } if (end * end <= x) { return end; } return start; } };