Appearance
二分法
1. 二分查找
2. x 的平方根
力扣题目链接https://leetcode.cn/problems/sqrtx/description/给定一个非负整数 x，计算并返回 x 的 算术平方根。由于返回类型是整数，结果只保留 整数部分，小数部分将被 舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。
示例 1：
输入：
x = 4输出：
2
示例 2：
输入：
x = 8输出：
2解释：8 的算术平方根是 2.82842...，由于返回类型是整数，小数部分将被舍去。
md
我们希望找到一个整数 mid，使得 mid _ mid 最接近 x 且小于等于 x。
二分查找的过程从 0 到 x（即 l = 0, r = x）之间不断缩小查找范围，直到找到最大的整数 mid，使得 mid _ mid <= x
1、如果 mid * mid <= x，说明 mid 可以作为一个候选平方根，此时我们记录 mid 并尝试进一步查找更大的数，调整左指针 l = mid + 1。
2、如果 mid * mid > x，说明 mid 太大，需要缩小搜索范围，调整右指针 r = mid - 1。js
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function (x) {
let l = 0,
r = x,
ans = -1
// 使用二分查找，查找平方根
while (l <= r) {
const mid = l + Math.floor((r - l) / 2) // 计算中间位置
if (mid * mid <= x) {
ans = mid // 记录当前可能的平方根
l = mid + 1 // 搜索右半边，寻找更大的平方根
} else {
r = mid - 1 // 搜索左半边，mid 太大
}
}
return ans // 返回最终找到的最大平方根
}