力扣-69-求开方

评论

题目：
69. Sqrt(x)(easy)

题目大意：
实现int sqrt(int x)函数。
计算并返回x的平方根，其中x是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

1
2
3
4
5
6
7
8
9
示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

解题思路：
一个数x的平方根肯定在[0,x]的范围内，0和1的平方根是它们自身，此外x的平方根sqrt满足:x / sqrt == sqrt。所以是在一个有序的集合中查找一个数，所以应该想到用二分查找。

二分查找中，有两种计算中值 m 的方式：
m = (l + h) / 2
m = l + (h - l) / 2
l + h 可能出现加法溢出，也就是说加法的结果大于整型能够表示的范围。但是 l 和 h 都为正数，因此 h - l 不会出现加法溢出问题。所以，最好使用第二种计算法方法。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int mySqrt(int x) {
    if(x <= 1) return x;
    int low = 1,high = x;
    while(low <= high){
        int mid = low + (high - low) /2;
        if(x/mid == mid){
            return mid;
        }else if(x/mid > mid){
            low = mid + 1;
        }else{
            high = mid - 1;
        }
    }
    return high;
    /*对于 x = 8，它的开方是 2.82842...，最后应该返回 2 而不是 3。在循环条件为 l <= h 并且循环退出时，h 总是比 l 小 1，也就是说 h = 2，l = 3，因此最后的返回值应该为 h 而不是 l*/
}

InstantCWeedStudent

个人简介。