题目描述
实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
链接 https://leetcode-cn.com/problems/sqrtx
理解
- 一个数的平方根肯定在
(0,num]区间内，而且此区间内的数字天然是按照升序"有序"排列的.- 那么就可以借助
"二分查找"的思想,每次缩短一半的查询范围来加速查找速度.
实现
public static int mySqrt(int x) {
//左边界
int left = 0;
//右边界
int right = x;
int searchNum = 0;
while (left <= right) {
//查找区间的中间数字
int mid = (left + right) / 2;
//FIXME 这块一定要注意int*int导致的数据越界.
//FIXME 在做乘法操作时,需要把 乘数或者被乘数转成long类型.
// 这样整个表达式的左右两侧都会采用long去做运算,避免出现因为int类型越界导致出错的问题
if ((long)mid * mid <= x) {
searchNum = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return searchNum;
复杂度
时间复杂度:因为借助的是二分查找的思想，所以复杂度为O(logn)
控件复杂度:O(1)
