69x 的平方根_69脳x

x 的平方根

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

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
由于返回类型是整数，小数部分将被舍去。
1
2
3
4
5
6
7
8
9
10

解题思路：从1~x循环，找到其平方等于x的值或大于x的的前一个值，循环采用二分，并且其实也没必要循环到x，我们发现1 2 3这三个数的平方根都是1，从4开始，我们只需要循环到x/2即可。

• 注意：如果使用int，范围会不够造成溢出，改成long long int即可。

int mySqrt(long long int x){
    if(x==0){
        return 0;
    }
    if(x>0&&x<4){
        return 1;
    }
    long long int low,heigh,mid,squre;
    low=0;
    heigh=(x%2==0)?(x/2):(x+1)/2;
    while(low<=heigh){
        mid=(low+heigh)/2;
        squre=mid*mid;
        if(squre==x){
            return mid;
        }
        else if(squre>x){
            heigh=mid-1;
        }
        else{
            low=mid+1;
            if((low*low)>x){
                return mid;
            }
        }
    }
    return mid;
}
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