题目描述
给你一个非负整数 x ,计算并返回 x 的算术平方根 。
由于返回类型是整数,结果只保留整数部分 ,小数部分将被舍去。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。
样例
输入:x = 4
输出:2
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
提示
0 <= x <= 2^31 - 1
算法1
二分查找,应注意是否会造成int溢出和除零的情况。
左边界设置为0,右边界设置为x,则直接在【0,x】这个范围内进行二分查找。
时间复杂度
logn
C++ 代码
class Solution {
public:
int binarySearch(int x) {
if (x == 0 || x == 1) return x;
int nLeft = 0, nRight = x;
while (nLeft <= nRight) {
int nMid = nLeft + ((nRight - nLeft) >> 1);
// 注意:x=0时,nMid=0,则会进行除0操作。x=1时,该种nMid计算方法也会进行除0操作。因此特判0和1
if (nMid == x / nMid) // 用除法,以防溢出
{
return nMid;
}
else if (nMid > x / nMid)
{
nRight = nMid - 1;
}
else
{
nLeft = nMid + 1;
}
}
return nRight;
}
int mySqrt(int x) {
/*
1、采用二分,左边界为0,右边界为2^16,但该值进行平方时容易溢出,因此可以考虑用负数范围去求取或者用除法(但注意除0)
2、如何舍去小数部分?当计算到小值时,会运行nLeft=nMid+1,此时走到大值,会运行nRight=nMid-1,则出现nLeft>nRight,直接退出循环,返回nRight即可
*/
return binarySearch(x);
}
};