69. Sqrt(x)

ugly binary search

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x, mid;
        if (x < 2)return x;
        while (l < r) {
            mid = l + (r - l) / 2;
            if (mid <= x / mid && (mid + 1) > x / (mid + 1)) return mid;    //pay attention to overflow mid*mid
            if (mid < x / mid) l = mid;
                else r = mid;
        }
        return mid;
    }
};

Newton's

    long r = x;
    while (r*r > x)
        r = (r + x/r) / 2;
    return r;