367. 有效的完全平方数-二分法

367. 有效的完全平方数

给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

进阶：不要 使用任何内置的库函数，如 sqrt 。

示例 1：

输入：num = 16
输出：true

示例 2：

输入：num = 14
输出：false

这题我们应该首先去想到二分法，这很重要，可以极大降低时间复杂度，我们可以多多学习这种方法：

bool isPerfectSquare(int num){
    int low=0;
    int high=num;
    long long p=(low+high)/2;
       //printf("%d ",p);
    while(p*p!=num&&low<=high){
        if(p*p>num){
            high=p-1;
            p=(low+high)/2;
        }
        else{
            low=p+1;
              p=(low+high)/2;

        }
    }
    printf("%d ",p);
    if(p*p==num){
        return true;
    }
    return false;
    

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29