https://leetcode.cn/problems/sqrtx/
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
示例 1:
输入:x = 4
输出:2
示例 2:
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示:
0 <= x <= 231 - 1
通过次数700,657提交次数1,815,1
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/sqrtx
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
类似题目:log N
思路:二分查找,当l==r查找结束。
要点在于l=mid r=mid-1 or l=mid+1 r=mid,本题舍小数,答案靠左 故选择l=mid r=mid-1
#define ll long long class Solution { public: int mySqrt(int x) { ll l=0, r = x; while(l!=r){ ll mid = (l+r+1)/2; if(mid*mid==x) return mid; else if(mid*mid>x){ // l = mid; r = mid-1; } else l = mid; } return l; } };
标签:示例,ll,mid,整数,69,平方根,小数 From: https://www.cnblogs.com/ygtzds/p/17196542.html