Sqrt x

技术文章 1年前 (2020) 完美者
329 0

标签:pre   cti   运算   一个   二分搜索   特殊   www   复杂度   另一个   

实现 int sqrt(int x) 函数

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

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

示例 1:

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

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

题解 - 二分搜索

由于只需要求整数部分,故对于任意正整数 , 设其整数部分为 , 显然有 1≤k≤x, 求解 k 的值也就转化为了在有序数组中查找满足某种约束条件的元素,显然二分搜索是解决此类问题的良方。

C++

class SqrtSolution {
public:
    int handle(int x) {
        if (x < 0) return -1;
        if (x == 0) return 0;
        long long start = 1;
        long long end = x;
        while(start + 1 < end) {
            long long mid = start + (end - start) / 2;
            if (mid*mid == x) {
                return mid;
            } else if (mid*mid < x) {
                start = mid;
            } else {
                end = mid;
            }
        }
        return start;
    }
};

源码分析

  • 异常检测,先处理小于等于0的值。
  • 使用二分搜索的经典模板,注意不能使用start < end, 否则在给定值1时产生死循环。
  • 最后返回平方根的整数部分start.

二分搜索过程很好理解,关键是最后的返回结果还需不需要判断?比如是取 start, end, 还是 mid? 我们首先来分析下二分搜索的循环条件,由while循环条件start + 1 < end可知,startend只可能有两种关系,一个是end == 1 || end ==2这一特殊情况,返回值均为1,另一个就是循环终止时start恰好在end前一个元素。设值 x 的整数部分为 k, 那么在执行二分搜索的过程中 start≤k≤end 关系一直存在,也就是说在没有找到 mid^2 == x 时,循环退出时有 start<k<end, 取整的话显然就是start了。

复杂度分析

经典的二分搜索,时间复杂度为 O(logn), 使用了startendmid变量,空间复杂度为 O(1).

除了使用二分法求平方根近似解之外,还可使用牛顿迭代法进一步提高运算效率,欲知后事如何,请猛戳 求平方根sqrt()函数的底层算法效率问题 -- 简明现代魔法,不得不感叹算法的魔力!

 

Sqrt x

标签:pre   cti   运算   一个   二分搜索   特殊   www   复杂度   另一个   

原文地址:https://www.cnblogs.com/lyc94620/p/13621338.html

版权声明:完美者 发表于 2020-09-17 16:12:07。
转载请注明:Sqrt x | 完美导航

暂无评论

暂无评论...