LeetCode 69. x 的平方根 and 浮点数平方根（二分）_leetcode原题 浮点数开根号

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

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

整数求平方根是下取整，因此判断条件是寻找满足条件的第一个数，注意题目中会给定： 2147395599 来求解平方根，会出现越界，因此使用long long 类型的数据。特判一下如果给定的数字是1，那么直接返回，如果mid*mid恰好等于给定的数字x，返回mid，其余情况都是向下取整得到的。

class Solution {
public:
    int mySqrt(int x) {
        int l=0,r=x/2;
        if(x==1) return 1;
        while(l<r)
        {
            long long mid=(l+r+1ll)>>1;
            if(mid*mid+0ll<=x+0ll) l=mid;
            else if(mid*mid==x) return mid;
            else r=mid-1;
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

浮点数二分是腾讯的一次面试题。
浮点数二分会出现0.01其平方根为0.1，比自己本身还大，因此左右边界扩大到[-1000,1000]，浮点数平方根会返回小数，因此使用double类型的数据。下面的代码终止条件是循环次数还可以是r-l<eps 其中eps=1e-6，该数字与保留精度位数有关（经验值），保留位数为4位，那么就是-6，保留位数为6位，那么为-8.
还要注意一点浮点数二分的时候没有整数二分那么复杂，mid没有加一这种操作。

#include<iostream>
using namespace std;
double n;
bool check(double mid)
{
    if(mid*mid>=n) return true;
    else return false;
}
int main()
{
    cin>>n;
    double l=-10000,r=10000;
    for(int i=0;i<100;i++)
    {
        double mid=(l+r)/2.0;
        if(check(mid)) r=mid;
        else l=mid;
        
    }
    
    printf("%.6f",l);
    return 0;
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24