【LeetCode-简单】69.x的平方根 + 367.有效的完全平方数 - 二分法

力扣题目链接

给定非负整数x，求x的算数平方根（只保留整数部分）

这个问题可以看成在区间 [0, x) 中寻找一个整数 target 使得 target * target 趋近于x

采用二分法，排除0与1这两个特殊情况后（不排除则left = 0, right = x;），确定左区间边界 left 为1，右区间边界 right 为 x/2（也可以是x）
在左闭右闭 [left, right] 区间内寻找x的算数平方根，即判断 (long long)mid * mid <= x ，这里要注意mid * mid存在可能溢出的情况，需要转换为long long。

代码：

class Solution {
public:
    int mySqrt(int x) {
    	//0, 1为特殊情况
        if(x == 0 || x == 1) return x;
        
        int left = 1, right = x / 2;
        int ans = 0;
        while(left <= right){
            int mid = left + (right - left)/2;
            if((long long)mid * mid <= x){
                ans = mid;
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

367.有效的完全平方数
这道题与上一道题思路一样

代码：

class Solution {
public:
    bool isPerfectSquare(int num) {
        if(num == 0 || num == 1){
            return true;
        }
        int left = 1, right = num / 2;
        while(left <= right){
            int mid = left + (right - left)/2;
            if((long long)mid * mid == num){
                return true;
            }else if((long long)mid * mid > num){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20