69. x 的平方根 - 力扣(LeetCode)
解法:二分查找
思路:看示例2:
可以看到8的平方根是2.82,在2^2和3^2之间,所以可以把数组分为两部分,(具有二段性)
而2.82去掉小数部分会变为2,所以返回值在 <x 的区间右端点上。
细节
1.此题没有数组,但可以直接用两个整数来模拟。
2.这一题的范围虽然在int范围内,但是中间判断逻辑是 1^2 2^2(1*1 2*2)这样的相乘逻辑,肯定会越界,所以用long long int.
3.边界情况:0,单独判断
class Solution
{
public:int mySqrt(int x) {if(x == 0)return 0;long long int left = 1,right = x;long long int mid = 0;while(left < right){//1.求区间右端点mid = left + (right - left + 1) /2;long long int mm = mid * mid;if(mm <= x)left = mid;elseright = mid - 1; }return left;}
};