尧图网页设计 
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇是「算法通关手册」AlgoNote针对 LeetCode 0069「x 的平方根」的专题题解聚焦「数学 二分查找」双考点在不借助浮点开方库的前提下仅用整数运算求出x平方根的整数部分。读完本篇你将掌握二分查找在「单调函数求最大可行值」场景下的标准模板、边界收缩细节与复杂度分析方法并能直接迁移到搜索插入位置、猜数字大小等同类二分题目。题目信息与考点题号0069力扣编号同时收录于剑指 Offer 专项突击版 LCR 072「x 的平方根」见 LCR 072 题解标签数学、二分查找难度简单仓库归属该题被同时收录在 二分查找题目分类列表、LeetCode 题目解析列表 以及 面试 100 题列表 / 面试 200 题列表 中属于高频面试考点。题目大意要求实现int sqrt(int x)函数。计算并返回 $x$ 的平方根只保留整数部分其中 $x$ 是非负整数。说明$0 \le x \le 2^{31} - 1$。题目只要求返回整数部分即向下取整的算术平方根 $\lfloor \sqrt{x} \rfloor$小数部分一律舍去不做四舍五入。示例示例 1输入x 4 输出2示例 2输入x 8 输出2 解释8 的算术平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。解题思路二分查找直接法为什么可以用二分查找因为要求解的是 $x$ 开方的整数部分所以可以从 $0 \sim x$ 的范围进行遍历找到 $k^2 \le x$ 的最大结果 $k$。关键在于单调性函数 $f(k) k^2$ 在非负整数域上随 $k$ 单调递增。因此满足 $k^2 \le x$这一条件具备二段性——存在一个分界点 $k^$使得所有 $k \le k^$ 都满足 $k^2 \le x$所有 $k k^*$ 都满足 $k^2 x$。这正是二分查找减而治之每轮排除一半不可能区间能够生效的前提对应仓库 二分查找一算法介绍 中数据必须有序 / 单调的适用条件。为了减少算法的时间复杂度我们使用二分查找的方法来搜索答案将线性遍历的 $O(x)$ 降为 $O(\log x)$。算法步骤初始化令左边界left 0右边界right x查找区间为闭区间 $[left, right]$。取中点计算mid (left right) // 2。判断并收缩若mid * mid x说明mid是可行解其平方不超过x用ans记录当前最优答案并继续在右半区间[mid 1, right]中寻找更大的可行解更新left mid 1否则说明mid的平方已经超过xmid及其右侧都不可能成为答案更新right mid - 1在左半区间[left, mid - 1]继续搜索。终止当left right时区间为空循环结束ans中保存的就是满足 $k^2 \le x$ 的最大整数 $k$。这里使用的正是仓库 二分查找二细节详解 中总结的「直接法」思路循环条件采用left right左闭右闭区间一旦区间为空直接返回记录下的ans。与直接返回left的写法如 0035. 搜索插入位置不同本题因为答案不一定是循环终止时的left最后一次满足条件时left已右移一位所以必须用ans变量持续记录最近一次可行的mid这是本题实现上的关键细节。代码class Solution: def mySqrt(self, x: int) - int: left 0 right x ans -1 while left right: mid (left right) // 2 if mid * mid x: ans mid left mid 1 else: right mid - 1 return ans边界情况推演以x 8为例逐步推演轮次leftrightmidmid*mid 8 ?动作108416 8 否right 320311 8 是ans 1left 232324 8 是ans 2left 343339 8 否right 2532—left right循环结束返回 ans 2结果与示例一致。再验证两个极值x 0时初始mid 00 * 0 0成立ans 0随后left 1 right 0退出正确返回0x 1时返回1同样正确。由于题目保证 $x \ge 0$ans的初值-1在正常流程中总会被覆盖但保留初值仍是一种防御性写法。实现细节补充防溢出与取值约定仓库的二分专题文档强调了几点可直接套用的工程细节mid计算mid (left right) // 2等价于mid left (right - left) // 2。虽然 Python 的整数不会溢出但在 C / Java / C 等语言中当left right接近整型上限本题x最大可达 $2^{31} - 1$left right最大约 $2^{32}$在 32 位环境下会溢出时推荐后一种写法以避免整型溢出区间约定统一采用左闭右闭区间[left, right]配合left right的循环条件与left mid 1/right mid - 1的收缩方式逻辑最不易出错单调性与二段性本题二分的前提是 $k^2$ 的单调性这一点与仓库中二分查找必须有序的适用条件完全对应。复杂度分析时间复杂度$O(\log n)$。每轮循环将查找区间缩小一半二分查找的时间复杂度为 $O(\log n)$其中 $n x$。空间复杂度$O(1)$。只用到了left、right、mid、ans等常数个变量无额外空间开销。思路扩展本题在二分模板中的定位结合仓库 二分查找一 与 二分查找二 的体系本题属于「直接法 左闭右闭」模板的典型变体它并不要求精确命中某个元素数组里不存在x的精确平方根而是要求满足不等式 $k^2 \le x$ 的最大整数。因此它更接近找右边界问题——每次找到可行解都记录并继续向右探测直到区间耗尽。理解了这一点就理解了ans变量存在的必要性也能自然迁移到「第一个错误的版本」「搜索插入位置」等题目。此外本题同样收录于剑指 Offer 专项LCR 072题面与解法完全一致见 LCR 072. x 的平方根刷题时可将两份题解对照学习。延伸练习0035. 搜索插入位置同样是找不到就返回应插入位置的边界型二分可直接体会return left与return ans两种收尾写法的差异0374. 猜数字大小经典的纯二分查找入门题完整二分查找题目列表见 00_06_categories_list.md。总结0069「x 的平方根」是一道以「数学」为外衣、以「二分查找」为内核的简单题利用 $k^2$ 的单调性在 $[0, x]$ 闭区间上二分搜索满足 $k^2 \le x$ 的最大整数并用ans变量持续记录最近一次可行解。其 $O(\log x)$ 时间、$O(1)$ 空间的复杂度表现配合防溢出的mid写法构成了可复用的标准模板——掌握本题等于掌握了二分查找处理最大可行值类问题的关键范式。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Go 题解69. Sqrt(x) —— 二分搜索与牛顿迭代法求整数平方根LeetCode Go 题解69. Sqrt x —— 二分搜索与牛顿迭代法求整数平方根 导读 本文基于 LeetCode Go https://link.g示例工程GitHub_Trending/leetcode1/leetcode数学技巧求平方根的牛顿迭代法详解GitHub_Trending/leetcode1/leetcode数学技巧求平方根的牛顿迭代法详解 你还在为求平方根的效率发愁吗从O n 到O log n示例工程教程数值的整数次方与平方根Learn-Algorithms 指数类算法面试题全解数值的整数次方与平方根Learn Algorithms 指数类算法面试题全解 导读 在 Learn Algorithms https://link.gitco教程上一篇零门槛蛋白质结构预测ColabFold带来的突破性可访问性革命下一篇如何选择正确的 Firecrawl 工具从单页抓取到批量处理的完整决策指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 AlgoNote 题解：LeetCode 0069「x 的平方根」——二分查找求整数平方根的完整解析
教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇是「算法通关手册」AlgoNote针对 LeetCode 0069「x 的平方根」的专题题解聚焦「数学 二分查找」双考点在不借助浮点开方库的前提下仅用整数运算求出x平方根的整数部分。读完本篇你将掌握二分查找在「单调函数求最大可行值」场景下的标准模板、边界收缩细节与复杂度分析方法并能直接迁移到搜索插入位置、猜数字大小等同类二分题目。题目信息与考点题号0069力扣编号同时收录于剑指 Offer 专项突击版 LCR 072「x 的平方根」见 LCR 072 题解标签数学、二分查找难度简单仓库归属该题被同时收录在 二分查找题目分类列表、LeetCode 题目解析列表 以及 面试 100 题列表 / 面试 200 题列表 中属于高频面试考点。题目大意要求实现int sqrt(int x)函数。计算并返回 $x$ 的平方根只保留整数部分其中 $x$ 是非负整数。说明$0 \le x \le 2^{31} - 1$。题目只要求返回整数部分即向下取整的算术平方根 $\lfloor \sqrt{x} \rfloor$小数部分一律舍去不做四舍五入。示例示例 1输入x 4 输出2示例 2输入x 8 输出2 解释8 的算术平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。解题思路二分查找直接法为什么可以用二分查找因为要求解的是 $x$ 开方的整数部分所以可以从 $0 \sim x$ 的范围进行遍历找到 $k^2 \le x$ 的最大结果 $k$。关键在于单调性函数 $f(k) k^2$ 在非负整数域上随 $k$ 单调递增。因此满足 $k^2 \le x$这一条件具备二段性——存在一个分界点 $k^$使得所有 $k \le k^$ 都满足 $k^2 \le x$所有 $k k^*$ 都满足 $k^2 x$。这正是二分查找减而治之每轮排除一半不可能区间能够生效的前提对应仓库 二分查找一算法介绍 中数据必须有序 / 单调的适用条件。为了减少算法的时间复杂度我们使用二分查找的方法来搜索答案将线性遍历的 $O(x)$ 降为 $O(\log x)$。算法步骤初始化令左边界left 0右边界right x查找区间为闭区间 $[left, right]$。取中点计算mid (left right) // 2。判断并收缩若mid * mid x说明mid是可行解其平方不超过x用ans记录当前最优答案并继续在右半区间[mid 1, right]中寻找更大的可行解更新left mid 1否则说明mid的平方已经超过xmid及其右侧都不可能成为答案更新right mid - 1在左半区间[left, mid - 1]继续搜索。终止当left right时区间为空循环结束ans中保存的就是满足 $k^2 \le x$ 的最大整数 $k$。这里使用的正是仓库 二分查找二细节详解 中总结的「直接法」思路循环条件采用left right左闭右闭区间一旦区间为空直接返回记录下的ans。与直接返回left的写法如 0035. 搜索插入位置不同本题因为答案不一定是循环终止时的left最后一次满足条件时left已右移一位所以必须用ans变量持续记录最近一次可行的mid这是本题实现上的关键细节。代码class Solution: def mySqrt(self, x: int) - int: left 0 right x ans -1 while left right: mid (left right) // 2 if mid * mid x: ans mid left mid 1 else: right mid - 1 return ans边界情况推演以x 8为例逐步推演轮次leftrightmidmid*mid 8 ?动作108416 8 否right 320311 8 是ans 1left 232324 8 是ans 2left 343339 8 否right 2532—left right循环结束返回 ans 2结果与示例一致。再验证两个极值x 0时初始mid 00 * 0 0成立ans 0随后left 1 right 0退出正确返回0x 1时返回1同样正确。由于题目保证 $x \ge 0$ans的初值-1在正常流程中总会被覆盖但保留初值仍是一种防御性写法。实现细节补充防溢出与取值约定仓库的二分专题文档强调了几点可直接套用的工程细节mid计算mid (left right) // 2等价于mid left (right - left) // 2。虽然 Python 的整数不会溢出但在 C / Java / C 等语言中当left right接近整型上限本题x最大可达 $2^{31} - 1$left right最大约 $2^{32}$在 32 位环境下会溢出时推荐后一种写法以避免整型溢出区间约定统一采用左闭右闭区间[left, right]配合left right的循环条件与left mid 1/right mid - 1的收缩方式逻辑最不易出错单调性与二段性本题二分的前提是 $k^2$ 的单调性这一点与仓库中二分查找必须有序的适用条件完全对应。复杂度分析时间复杂度$O(\log n)$。每轮循环将查找区间缩小一半二分查找的时间复杂度为 $O(\log n)$其中 $n x$。空间复杂度$O(1)$。只用到了left、right、mid、ans等常数个变量无额外空间开销。思路扩展本题在二分模板中的定位结合仓库 二分查找一 与 二分查找二 的体系本题属于「直接法 左闭右闭」模板的典型变体它并不要求精确命中某个元素数组里不存在x的精确平方根而是要求满足不等式 $k^2 \le x$ 的最大整数。因此它更接近找右边界问题——每次找到可行解都记录并继续向右探测直到区间耗尽。理解了这一点就理解了ans变量存在的必要性也能自然迁移到「第一个错误的版本」「搜索插入位置」等题目。此外本题同样收录于剑指 Offer 专项LCR 072题面与解法完全一致见 LCR 072. x 的平方根刷题时可将两份题解对照学习。延伸练习0035. 搜索插入位置同样是找不到就返回应插入位置的边界型二分可直接体会return left与return ans两种收尾写法的差异0374. 猜数字大小经典的纯二分查找入门题完整二分查找题目列表见 00_06_categories_list.md。总结0069「x 的平方根」是一道以「数学」为外衣、以「二分查找」为内核的简单题利用 $k^2$ 的单调性在 $[0, x]$ 闭区间上二分搜索满足 $k^2 \le x$ 的最大整数并用ans变量持续记录最近一次可行解。其 $O(\log x)$ 时间、$O(1)$ 空间的复杂度表现配合防溢出的mid写法构成了可复用的标准模板——掌握本题等于掌握了二分查找处理最大可行值类问题的关键范式。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode-Go 题解69. Sqrt(x) —— 二分搜索与牛顿迭代法求整数平方根LeetCode Go 题解69. Sqrt x —— 二分搜索与牛顿迭代法求整数平方根 导读 本文基于 LeetCode Go https://link.g示例工程GitHub_Trending/leetcode1/leetcode数学技巧求平方根的牛顿迭代法详解GitHub_Trending/leetcode1/leetcode数学技巧求平方根的牛顿迭代法详解 你还在为求平方根的效率发愁吗从O n 到O log n示例工程教程数值的整数次方与平方根Learn-Algorithms 指数类算法面试题全解数值的整数次方与平方根Learn Algorithms 指数类算法面试题全解 导读 在 Learn Algorithms https://link.gitco教程上一篇零门槛蛋白质结构预测ColabFold带来的突破性可访问性革命下一篇如何选择正确的 Firecrawl 工具从单页抓取到批量处理的完整决策指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考