LeetCode 69. x 的平方根 【二分查找】
发布日期:2021-06-29 14:32:18
浏览次数:2
分类:技术文章
本文共 749 字,大约阅读时间需要 2 分钟。
题目描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4
输出: 2 示例 2:输入: 8
输出: 2 说明: 8 的平方根是 2.82842…,- 由于返回类型是整数,小数部分将被舍去。
解题思路
我们可以把这道题想象成,给定一个非负整数 a,求 f(x) = x2 −a = 0 的解。因为我们只考虑 x ≥ 0,所以 f(x)在定义域上是单调递增的。考虑到 f(0) = −a ≤ 0,f(a) = a2 −a ≥ 0,我们可以对[0,a]区间使用二分法找到 f(x) = 0的解。
注意,在以下的代码里,为了防止除以0,我们把 a = 0的情况单独考虑,然后对区间[1,a] 进行二分查找。
使用了左闭右闭的写法。
AC
class Solution { public: int mySqrt(int x) { if(x==0) return 0; long left=1,right=x,ans; long mid; while(left<=right){ mid = (left+right)/2; ans = x/mid; if(ans == mid) return ans; else if(ans < mid) right = mid-1; else left = mid+1; } return right; }};
转载地址:https://chocolate.blog.csdn.net/article/details/106207016 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年05月01日 06时29分41秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
为什么说卷积神经网络,是深度学习算法应用最成功的领域之一?
2019-04-29
在电网工作,有多高大上?
2019-04-29
「2020年大学生电子设计竞赛分享」电源题,省一等奖!
2019-04-29
又一国产开源微内核操作系统上线!源代码已开放下载
2019-04-29
10年老兵!从大学毕业生到嵌入式系统工程师的修炼之道……
2019-04-29
如何才能学好单片机?
2019-04-29
一根网线有这么多“花样”,你知道吗?
2019-04-29
雷军1994年写的诗一样的代码,我把它运行起来了!
2019-04-29
2020年大学生电子设计竞赛,B题,单相在线式不间断电源,详细技术方案!
2019-04-29
大佬终于把鸿蒙OS讲明白了,收藏了!
2019-04-29
中国35位“大国工匠”榜单出炉!西工大、西电合计占半壁江山!清华仅1人!...
2019-04-29
知乎热议:嵌入式开发中C++好用吗?
2019-04-29
这100道Linux常见面试题,看看你会多少?
2019-04-29
嵌入式开发中常用的几种通信接口总结
2019-04-29
什么?电路板上还要喷漆?
2019-04-29
读博读废了是种什么样的体验?
2019-04-29
2020年,技术圈十大“翻车”事件!
2019-04-29
C语言状态机编程思想
2019-04-29
为什么很多电器设备都要使用单片机?
2019-04-29
在中国做操作系统研发 20 年是种什么体验?
2019-04-29