手撕sqrt() （可以不看，拓竹常考
1. 二分法的基本思路
二分法（Binary Search）用于在一个已知范围内，逐渐缩小范围，找到一个满足某种条件的值。在求平方根的过程中，二分法的目标是找出一个数 mid，使得 mid * mid 尽可能接近 x，即 mid 是 x 的平方根。
2. 初始化搜索范围
我们知道平方根的值一定在 [0, x] 或者 [0, 1] 之间。比如：
对于
x = 9，平方根在[0, 9]范围内。对于
x = 0.25，平方根在[0, 1]范围内。
根据 x 的大小，我们初始化了左右区间：
low = 0
high = x (如果
x >= 1)，如果x < 1，high设置为1，这是为了避免误差问题。
3. 循环条件 **high - low > epsilon**
我们希望通过不断缩小 low 和 high 的差值来逼近平方根的值。精度 epsilon 设定了我们希望得到的精度范围。
epsilon：它定义了二分法停止的精度。比如1e-7就表示当我们找到的low和high的差值小于0.0000001时，我们就认为结果已经足够精确。为什么是
high - low > epsilon？精度控制：当
high和low的差值小于设定的精度时，说明我们已经找到了一个非常接近x的平方根，进一步的搜索就没有意义了。缩小范围：每次迭代时，我们都会将
low和high的范围缩小一半，因此循环会逐步减少误差，直到达到预定的精度。
4. 更新搜索范围
每次计算中间值 mid，然后检查 mid * mid 和 x 的关系：
如果
mid * mid > x，说明平方根在mid左侧，因此将high = mid。如果
mid * mid < x，说明平方根在mid右侧，因此将low = mid。
通过这种方式，我们不断缩小 low 和 high 的区间，逐渐逼近真实的平方根。
5. 为什么最后返回 **low** 和 **high** 的平均值？
由于每次迭代都在缩小 low 和 high 的范围，当它们的差值小于 epsilon 时，说明 low 和 high 已经非常接近真实的平方根。在这种情况下，low 和 high 都是平方根的近似值，但它们并不完全相等。
为了进一步提高精度，我们取 low 和 high 的平均值作为最终的结果。这样可以确保返回的是两者之间的最佳近似值。简单来说，当 low 和 high 越来越接近时，它们的平均值就是我们要找的平方根。
总结：
epsilon是精度控制参数，确定了循环何时停止。high - low > epsilon是判断二分法是否还需要继续缩小搜索范围，直到low和high足够接近，满足所需精度。返回 **
(low + high) / 2** 是因为经过多次迭代后，low和high已经非常接近平方根，我们返回它们的平均值，作为平方根的近似值。
这种方法的核心就是通过不断缩小搜索区间，逼近真实的平方根，直到满足精度要求。
function sqrt(x) {
if (x < 0) {
return NaN
}
if (x === 0 || x === 1) {
return x; // 0和1的平方根直接返回
}
let low = 0;
let high = x;
let epsilon = 1e-7; // 精度控制
// 如果x小于1，右边界high设为1
if (x < 1) {
high = 1;
}
while (high - low > epsilon) {
let mid = (low + high) / 2;
let midSquared = mid * mid;
if (midSquared > x) {
high = mid; // 说明平方根小于mid
} else {
low = mid; // 说明平方根大于mid
}
}
return (low + high) / 2; // 返回low和high的平均值，作为平方根
}
console.log(sqrt(9)); // 输出: 3
console.log(sqrt(2)); // 输出: 1.4142135623746899
console.log(sqrt(0.25)); // 输出: 0.5
console.log(sqrt(0)); // 输出: 0以上是小数模式
以下是整数模式
核心原理：循环不变量
在整个二分查找过程中，始终维护以下不变量：
left的平方 可能 小于等于 x，也可能大于 xright的平方 始终 小于等于 x（初始时right = x，但x²可能大于 x，所以初始时这个不变量需要验证）
更准确地说，循环结束时：
left是第一个满足left² > x的整数right = left - 1，且right² ≤ x
为什么一定能保证？
关键在于二分查找的结束条件和移动规则：
while (left <= right) {
let mid = left + ((right - left) >> 1)
if (mid * mid < x) {
left = mid + 1 // 当 mid² < x，left 向右移动
} else {
right = mid - 1 // 当 mid² >= x，right 向左移动
}
}两种情况分析
情况1：mid² < x
此时
mid的平方小于 x，说明mid太小了真正的平方根在
mid右侧所以
left = mid + 1，排除掉 **mid** 及左侧所有元素
情况2：mid² >= x
此时
mid的平方大于等于 x，说明mid太大了或正好相等真正的平方根在
mid左侧（包括mid本身如果正好相等）所以
right = mid - 1，排除掉 **mid** 及右侧所有元素
关键洞察
当循环结束时（left > right），我们可以推导出：
right** 是最后一个 **right² ≤ x** 的数**因为每次移动
right时，都是因为mid² ≥ x，我们将right移到了mid - 1而被排除的
mid本身就满足mid² ≥ x所以所有被排除的数（≥ mid）平方都 ≥ x
剩下的
right自然就是最后一个平方 ≤ x 的数
left = right + 1循环结束时
left > right，且每次只移动一步所以
left = right + 1
left² > x** 必然成立**因为
left = right + 1而
right是最后一个平方 ≤ x 的数所以
right + 1（即left）就是第一个平方 > x 的数
实例追踪
x = 8 的完整过程
| 步骤 | left | right | mid | mid² | 比较 | 操作 |
|---|---|---|---|---|---|---|
| 1 | 0 | 8 | 4 | 16 | 16≥8 | right=3 |
| 2 | 0 | 3 | 1 | 1 | 1<8 | left=2 |
| 3 | 2 | 3 | 2 | 4 | 4<8 | left=3 |
| 4 | 3 | 3 | 3 | 9 | 9≥8 | right=2 |
| 结束 | 3 | 2 | - | - | - | left>right |
right = 2，2² = 4 ≤ 8✅left = 3，3² = 9 > 8✅left = right + 1✅
x = 9 的完整过程
| 步骤 | left | right | mid | mid² | 比较 | 操作 |
|---|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 16 | 16≥9 | right=3 |
| 2 | 0 | 3 | 1 | 1 | 1<9 | left=2 |
| 3 | 2 | 3 | 2 | 4 | 4<9 | left=3 |
| 4 | 3 | 3 | 3 | 9 | 9≥9 | right=2 |
| 结束 | 3 | 2 | - | - | - | left>right |
right = 2，2² = 4 ≤ 9✅left = 3，3² = 9 = x，这里left² = x而不是 > x等等！这里出现了特殊情况
重要修正
当 x 是完全平方数时（如 9），循环结束时：
left = 3，left² = 9 = x，不是大于 xright = 2，right² = 4 < x
所以准确的说法应该是：
循环结束时，**left** 是第一个满足 **left² ≥ x** 的整数，**right = left - 1** 满足 **right² < x**
验证
当
x = 8（非完全平方）：left=3，3²=9 ≥ 8✅，right=2，2²=4 < 8✅当
x = 9（完全平方）：left=3，3²=9 ≥ 9✅，right=2，2²=4 < 9✅
最终返回逻辑解释
return left * left > x ? left - 1 : left如果
left² > x：说明 x 不是完全平方数，平方根是left - 1如果
left² <= x：说明 x 是完全平方数，平方根就是left
这个判断实际上等价于：
return left * left > x ? left - 1 : left
// 等价于
return right // 因为 right = left - 1因为当 left² > x 时，答案就是 left - 1 = right
当 left² = x 时，答案就是 left（此时 right = left - 1 是错的）
所以更简洁的写法应该是：
return right // 但这样当 x 是完全平方数时会返回 left-1，错误！
// 所以必须用原写法核心就是二分查找保证结束时 left 是第一个平方 ≥ x 的数。
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
let low = 0
let high = x
if(x == 0 || x == 1){
return x
}
while(low <= high){
let mid = Math.floor((high + low)/2)
let midSquared = mid*mid
if(midSquared < x){
//平方根小于mid
low = mid + 1
}else{
high = mid - 1
}
}
return low * low > x ? low -1 : low
};手撕 call stack最大化（忘记哪家的了
“手撕”实现 Call Stack 最大化，实际上是在考察你对 JavaScript 执行上下文、调用栈 和 异步操作 的理解。一般来说，我们可以通过不断地递归调用来将调用栈推到最大。
原理
JavaScript 的调用栈（Call Stack）用于管理函数调用，栈的大小受到浏览器的限制。如果你不断嵌套函数调用，栈会逐渐增大，直到超出浏览器的最大栈深度，导致“栈溢出”（stack overflow）。
示例代码
function recursive() {
// 自己调用自己，不断递归
recursive();
}
try {
recursive();
} catch (e) {
console.log("Stack overflow occurred!");
}解释：
递归调用：每次调用
recursive()都会让函数压入调用栈，栈的深度增加。栈溢出：当递归调用的层数超过浏览器的栈深度限制时，会抛出栈溢出错误
Stack overflow occurred!。异步避免溢出：如果你用异步操作（比如
setTimeout或Promise）则调用栈会在执行时被清空，能够避免栈溢出，但这样就不符合最大化栈的要求。
实现一个能测量当前环境最大调用栈深度的函数。
let count = 0;
function measureStack() {
try {
count++;
return measureStack();
} catch (e) {
return count;
}
}
console.log(measureStack()); // 输出当前环境的最大调用深度