105.x 的平方根
题目
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1：
- 输入：x = 4
- 输出：2
示例 2：
- 输入：x = 8
- 输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
思路
我们在猜一个数 mid，看 mid × mid 会不会超过 x。
如果：
- mid × mid == x，说明刚好猜中
- mid × mid < x，说明 mid 可能是答案，但还可以试试更大的
- mid × mid > x，说明 mid 太大了，要往小了猜
这就是二分查找。
为了避免 mid * mid 太大导致溢出，我们不用 mid * mid <= x，而用：
mid <= x / mid
意思完全一样，但更安全。
class Solution {
fun mySqrt(x: Int): Int {
// 0 和 1 的平方根就是它自己
if (x < 2) return x
var left = 1
// 最大不可能超过中间的数
var right = x / 2
var answer = 0
// 在 left 到 right 之间不断猜答案
while (left <= right) {
// 取中间值
val mid = left + (right - left) / 2
// 如果 mid <= x / mid
// 说明 mid * mid <= x
// mid 没有超过平方根，可能是答案
if (mid <= x / mid) {
answer = mid
// 继续往右找，看有没有更大的合法答案
left = mid + 1
} else {
// 说明 mid * mid > x
// mid 太大了，要往左找
right = mid - 1
}
}
return answer
}
}
复杂度
- 时间复杂度: O(log x)，二分查找次数约为 log₂ x。
- 空间复杂度: O(1)。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!