【CSDN Daily Practice】【二分】X的平方根

【CSDN Daily Practice】【二分】X的平方根

• 官方思路：经典二分法，傻白甜地给了个最大值46340
• 建议思路：使用渐进二分法，不断逼近所求的平方根（不需要定义最大值）

class Solution {
    public int mySqrt(int x) {
        int left = 0, right = 46340;
        while (left < right) {
            int mid = (left + right) / 2;//建议使用left + (right-left)>>>1
            if (mid * mid < x)
                left = mid + 1;
            else if (mid * mid > x)
                if ((mid - 1) * (mid - 1) <= x) // 往小一值探测
                    return mid - 1;
                else
                    right = mid - 1;
            else
                return mid;
        }
        if (left * left > x)
            return left - 1;
        return left;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public int mySqrt2(int x) {
        int k = 0;
        int step = x/2;
        while (step >= 1) {
            while((k+step)*(k+step) <= x){
                k += step;//逼近
            }
            step /= 2; //砍半
        }
        return k ;
    }
1
2
3
4
5
6
7
8
9
10
11