不用库函数求平方根(二分与牛顿法)
哪些公司问过
答案要点
- 二分法:在 [0, max(1,x)] 区间里比较 mid² 与 x,收缩边界
- 浮点终止条件:区间宽度小于 eps 或迭代固定次数,复杂度 O(log(1/eps))
- 整数平方根:边界相遇时返回,注意 mid*mid 溢出,可改用 mid 与 x/mid 比较
- 牛顿法:x = (x + a/x) / 2,a 为被开方数,迭代至收敛,二次收敛,速度很快
- 边界:x 为 0 或 1 直接返回,负数无实根
易错点
- 没有处理 0、1 和负数
- 整数二分时 mid*mid 溢出
- 浮点二分用相等判断终止,而不是精度
- 牛顿法初值取 0,导致除零
面试官常见追问
- 牛顿法为什么收敛快?
- 二分法求根号 2 要迭代多少次?
- mid * mid 溢出怎么避免?
- 牛顿法的初值怎么选?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。