69. Sqrt(x)

binary search O(logx)

class Solution {
public:
    int mySqrt(int x) {
        long lo = 0, hi = x; // 一定要从0开始
        while (lo < hi) { // 这道题用小于比较好（<=也行）因为不一定取到精确值
            long m = (lo + hi + 1) / 2, s = m * m; // 注意必须是long防止溢出，并且要+1来取m
            if (s <= x) {
                lo = m;
            } else {
                hi = m - 1;
            }
        }
        return lo;
    }
};

class Solution {
public:
    int mySqrt(int x) {
        long min = 0, max = x;
        while (min <= max) { // 一定是min <= max而不是min < max是因为最后一定要是min > max来跳出循环，min == max是合法的
            long mid = (min + max) / 2;
            long p = mid * mid;
            if (p == x) {
                return mid;
            }
            else if (p < x) {
                min = mid + 1;
            }
            else {
                max = mid - 1;
            }
        }
        return max; // 是max而不是min是因为最后二分查找一定结束在一个较小的数上，比如5是2而不是3，10是3而不是4，而min一定要比max大才能跳出while循环
    }
};

newton’s method O(logx)

class Solution {
public:
    int mySqrt(int x) {
        long r = x;
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        return r;
    }
};

double版

double s(double x) {
	double lo = 0, hi = max(x, 1.0);
	while ((hi - lo) > 1e-8) {
		auto m = (lo + hi) / 2, p = m * m;
		if (p <= x) {
			lo = m;
		} else {
			hi = m;
		}
	}
	return lo;
}