今天做一个面试中出现概率比较高的算法题——求某个数的平方根。

情景一

题目描述

给定一个非负整数 x ，计算并返回 x 的算术平方根 。

函数为：

int sqrt（ int x ）

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

要求不允许使用任何内置指数函数和算符，比如 pow(x, 0.5) 或者 x ** 0.5 。

解题分析

对于求 x的平方根的整数部分k，则k满足 k^2 <= x 中的最大值。

对于k的范围一定在0~x中，既然要从0~x中寻求 满足 k^2 <= x 中k的最大值，我们可以只用二分查找的方式寻求k值。

二分查找中，经过不断比较中间值是否满足条件而进行不断的调整上下界的范围，从而得到最终的结果。

算法实现

int sqrt(int x){

    int r = x;
    int low = 0;
    int high = x;

    //采用二分法进行计算
    while( low <= high )
    {
        //获取中间值
        int mid = (low + high)/2;
        //若中间值的平方小于x, 说明mid过小，则从mid到high之间找值
        if( (long) mid * mid <= x )
        {
            r = mid; // 记录返回值
            low = mid + 1;
        }
        else //若中间值的平方大于x, 说明mid过大，则从low到mid之间找值
        {
            high = mid - 1;

        }
    }

    return r;
}

复杂度分析

• 时间复杂度：O(log x)，也即是二分查找需要的次数。
• 空间复杂度：O(1) 。

情景二

写一个函数求平方根，该函数带2个参数，第一个参数是目标数字，第二个参数是精度。

double sqrt(double target, double g);
要求 |a^2 - t| < g

解题分析

本题解析也是使用二分法，思路如上题，该算法的实现不过是对返回结果要求了精度限制。

还有一种方式是 第二个参数为 int，要求返回小数点后多少位，原理都是一样的。

代码实现

#include <stdio.h>

#define myabx(x) (((x)>0) ? (x) : (-x))

double mysqrt(double target, double g)
{

//由于纯小数开方大于其本身，所以若是纯小数，取值范围为[target, 1], 若大于1，取值范围为[0, target]
double low = target > 1 ? 0 : target;
double high = target > 1 ? target : 1;

double mid = (low + high)/2;
double diff = mid*mid - target;
//保证求得的结果在[-g, g] 范围内
while(myabx(diff) > g)
{
//说明mid过大，应该进一步缩小范围
if(diff > 0)
{
high = mid;

}
else //说明mid过小，应该进一步扩大取值范围 
{
low = mid;
}

mid = (low + high)/2;
diff = mid*mid - target;
}

return mid;

}


int main()
{

printf(" 2.0 : %f\n", mysqrt(2.0, 0.0001));
printf(" 4.0 : %f\n", mysqrt(4.0, 0.0001));
printf(" 7.0 : %f\n", mysqrt(7.0, 0.0001));
printf(" 0.2 : %f\n", mysqrt(0.2, 0.0001));
printf(" 0.5 : %f\n", mysqrt(0.5, 0.0001));

return 0;
}

结果如下：

2.0 : 1.414185
4.0 : 2.000000
7.0 : 2.645748
0.2 : 0.447266
0.5 : 0.707153

对于 sqrt() 方法的实现，本文章只采用了比较常见的二分法来解题，还有别的数学算法可以解决，比如牛顿迭代法等，该方法的收敛性比二分法好。若对牛顿迭代法感兴趣，可以自行百度了解学习。