x 的平方根

1
class Solution {
2
public:
3
    int mySqrt(int x) {
4
        if (x == 0) return 0;
5
        if (x == 1) return 1;
6

7
        int i;
8
        // 注意：为避免 i * i 导致整型溢出，我们使用 x / i 来进行比较
9
        for (i = 1; i < x; i++) {
10
            if (i <= x / i && (i + 1) > x / (i + 1)) {
11
                break;
12
            }
13
        }
14
        return i;
15
    }
16
};

1
class Solution {
2
public:
3
    int mySqrt(int x) {
4
        if (x == 0) return 0;
5
        int left = 1, right = x;
6

7
        while (left < right) {
8
            // 取中点时 +1 是为了在只有两个元素时向上取整，配合 left = mid 避免死循环
9
            int mid = left + (long)(right - left + 1) / 2;
10

11
            if (mid <= x / mid) {
12
                left = mid;      // mid 可能是答案，尝试向右侧逼近
13
            } else {
14
                right = mid - 1; // mid 太大了，缩减右边界
15
            }
16
        }
17
        return left;
18
    }
19
};