69-x的平方根

LeetCode 69. Sqrt x

LeetCode-69

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

method: 二分法

模板二：满足条件的最大数
r和l相加可能超过int，所以用long
两个mid相乘也可能越界，把一个除到另一边去

int mySqrt(int x) {
    unsigned long l = 0, r = x;
    while (l < r) {
        unsigned long mid = l + r + 1 >> 1;      // 左移一位就相当于除以2
        if (mid <= x / mid) l = mid;    // 把乘移到另一边
        else r = mid - 1;
    }
    return l;
}

时间复杂度：$O(logx)$