019 x 的平方根
题目描述： 给定一个非负整数 x，计算并返回 x 的平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
思路一：暴力解法
最直观的想法是从 0 开始依次枚举，直到找到满足条件的数。这里不需要纠结枚举到 x/2 还是 x，因为一旦找到结果直接返回即可。
（1）如果 i * i == x，直接返回 i； （2）如果 i * i > x，说明之前的一个数是结果，返回 i - 1。
需要注意一点：i * i 可能会超过 int 的最大值，因此计算时建议使用 long long 类型来防止溢出。
代码实现：
class Solution {
public:
int mySqrt(int x) {
// 防止乘法溢出，使用 long long 类型
long long i = 0;
for (i = 0; i <= x; i++) {
if (i * i == x) return i;
if (i * i > x) return i - 1;
}
return -1;
}
};
时间复杂度：O(n)，空间复杂度：O(1)。
思路二：二分查找
既然暴力法效率较低，我们可以利用单调性优化。设 x 的平方根结果为 index，那么：
- [0, index] 之间的元素，平方后都小于等于 x；
- [index + 1, x] 之间的元素，平方后都大于 x。
这符合二分查找的特征，可以将时间复杂度降低到 O(log n)。
代码实现：
class Solution {
public:
int mySqrt(int x) {
if (x < 1) return 0;
int left = , right = x;
(left < right) {
mid = left + (right - left + ) / ;
(mid * mid <= x) {
left = mid;
} {
right = mid - ;
}
}
left;
}
};
