每日一题
LCR 072. x 的平方根

给定一个非负整数 `x` ，计算并返回 `x` 的平方根，即实现 `int sqrt(int x)` 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。



**示例 1:**

```
输入: x = 4
输出: 2
```

**示例 2:**

```
输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2
```

解法一：二分查找

时间复杂度：O(logn)

空间复杂度：O(1)
class Solution {
public:
int mySqrt(int x) {
if(x == 0) return 0;
int left, right;
for(left = 1, right = x; left < right; )
{
int mid = left + (right - left + 1) / 2;
if(mid <= x / mid) left = mid;
else right = mid - 1;
}
return left;
}
};