Leetcode 69.x的平方根【C++】

地址：https://leetcode-cn.com/problems/sqrtx/

题目

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

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

解题思路

采用二分法求解。

平方根一定是 >= 0 的，则 low 取初始值为0；平方根不大于这个数的一半再+1，所以 up 取初始值为 x / 2.0 + 1.0，然后两头向中间逼近。题目要求只保留整数部分，小数部分舍去，所以平方根将最终的 mid 取整。

代码

class Solution {
public:
    int mySqrt(int x) {
        double low = 0;//平方根一定是 >= 0 的
        double up = x / 2.0 + 1.0;//平方根不大于这个数的一半再+1
        double mid;
        while (int(low) != int(up))
        {
            mid = (low + up) / 2.0;
            if (mid * mid > x)
                up = mid;
            else if (mid * mid < x)
                low = mid;
            else
                return int(mid);
        }
        return int(mid);
    }
};