Ninjiacoder Swift Lover, Fullstack Developer

实现一个开方算法

题目

昨天参加美团三面,有一道算法设计题,题目是这样的

func sqrt(x: Double) -> Double

实现一个方法,输入输出为Double类型,方法的功能是返回输入值X的开方,不能调用接口,不需要想数学方法,仅需简单的算法进行实现。

第一步

拿到这道题,面试官给我3min时间思考,一上来就有思路,用二分来解决,那么首先要确定二分的左右边界是什么,这里就要注意了,X<1X>1的情况要分开来考虑:

  • X<1 时,左边界为X,右边界为1;
  • X>1 时,左边界为1,右边界为X;

第二步

当我把这个思路和面试官说完以后,面试官对这一步骤表示认可,于是抛出下一个问题,二分什么时候退出呢?然后我下意识的问了一句,有什么精度要求嘛?面试官答,那我们就要求精度为1e-8 吧。

我一开始把精度理解成了保留小数点后几位,于是尴尬的事情发生了:

我的第一想法是,把二分的结果乘以1e-8,然后看它是不是整数,被面试官否定了。

我的第二想法是,把二分的结果转换成字符串,然后判断位数,又被否定了。

面试官于是给出提示,从二分本身考虑,于是想到,所谓精度只是一个误差范围,那么在二分过程中,如果左右边界之差小于1e-8就意味着达到了精度。

以上就是整个算法的思路

第三步

第三步是要求分析这个算法的复杂度,我计算的时候直接给出了这样的公式

2^n * 10^-8 = |x-1|

完整代码

回去之后用 Swift 实现了一遍

func sqrt(x: Double) -> Double { 
    if (x < 1) {
        return half(left: x, right: 1, x: x)
    } else if (x > 1) {
        return half(left: 1, right: x, x: x)
    } else {
        return 1
    }
}

func half(left: Double, right: Double, x: Double) -> Double {
    let middle = (left + right) / 2
    if (right - left < 1e-8) {
        return middle
    }
    if (middle * middle < x) {
        return half(left: middle, right: right, x: x)
    } else if (middle * middle > x) {
        return half(left: left, right: middle, x: x)
    } else {
        return middle
    }
}