今天做一个面试中出现概率比较高的算法题——求某个数的平方根。
情景一
题目描述
给定一个非负整数 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() 方法的实现，本文章只采用了比较常见的二分法来解题，还有别的数学算法可以解决，比如牛顿迭代法等，该方法的收敛性比二分法好。若对牛顿迭代法感兴趣，可以自行百度了解学习。
