LeetCode二分查找:x 的平方根
题目描述
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
**注意:**不允许使用任何内置指数函数和算符,例如 pow(x, 0.5)
或者 x ** 0.5
。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
解题思路
用二分查找的思想,通过不断缩小搜索范围,最终找到平方根的整数部分。
需要注意得一点是:在计算 mid
时使用 left+(right-left) / 2
,而不是 (left + right) / 2
。这样可以避免溢出。
代码
class Solution {
public int mySqrt(int x) {
long high = x / 2;
long low = 0;
if (x == 1) {
return 1;
}
while (low <= high) {
long mid = low + (high - low) / 2;
long r = mid * mid;
if (r > x) {
high = mid - 1;
} else if (r < x) {
low = mid + 1;
} else {
return (int) mid;
}
}
// 返回 low - 1 而不是 low
return (int) (low - 1);
}
}
原文地址:https://blog.csdn.net/qq_45103836/article/details/134764029
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_38388.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。