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

情景一

标题问题描述

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

函数为：

int sqrt（ int x ）

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

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

解题阐发

关于求 x的平方根的整数部门k，则k满足 k² <= x 中的更大值。

关于k的范畴必然在0~x中，既然要从0~x中寻求 满足 k² <= 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.4141854.0 : 2.0000007.0 : 2.6457480.2 : 0.4472660.5 : 0.707153

关于 sqrt() 办法的实现，本文章只接纳了比力常见的二分法来解题，还有此外数学算法能够处理，好比牛顿迭代法等，该办法的收敛性比二分法好。若对牛顿迭代法感兴趣，能够自行百度领会进修。