一个算法题
要求用二分查找实现
public double sqrt(int num){
//实现
}
/**
* 二分查找 求平方根
* @param num
* @return
*/
public double sqrt(int num) {
//这个题应该要看精度 如果没有特殊的精度要求
double low = 0;
double high = num;
while (low < high) {
double mid = (low + high) / 2;
if ((mid * mid) > num) {
high = mid;
} else if ((mid * mid) < num) {
low = mid;
} else {
// mid * mid == num 因为我做这个题目时候会觉得这个条件可能永远不会成立
// 但是 double 类型存在一个精度问题
// 当 mid 的精度到达一定位置时候 mid * mid 会得到一个整数 其刚好是 num 的近似平方根
return mid;
}
}
return -1;
}
这个题目 当时是没有精度要求的,我根本就想不到 两个 double 相乘,在一定精度情况下居然能够得到一个整数, 当然我理解其中的原理,由于二进制长度限制,有限的位置不可能表示无限精度的小数,所以其乘法运算可能会出现溢出的情况,然后乘法运算溢出后的结果刚刚是一个整数。
1
yuankui 2020-01-19 18:39:01 +08:00
面试官正在为自己想到这么优秀的解法而骄傲
|
2
lewis89 OP @yuankui #1 这个解法是我事后想到的,出题的事后 他也没讲精度,没有精度约束的话 只能这样求解,但是我又不敢这样写。
|
3
RtIHZ 2020-01-19 19:06:26 +08:00 1
```
const double DELTA = 0.000001; if (abs(mid * mid - num) < DELTA) { // ... } ``` |
4
InkStone 2020-01-19 19:06:35 +08:00
我觉得你想多了,面试官可能单纯是想让你用牛顿法……
|
5
RtIHZ 2020-01-19 19:08:03 +08:00
这题我觉得出的没毛病。
|
6
InkStone 2020-01-19 19:08:53 +08:00
或者就像三楼那么写二分,完全没有问题。楼主你事后想出来的这个写法有 UB,肯定不能这么写的……
|
9
also24 2020-01-19 19:11:50 +08:00
既然你已经意识到了精度问题,那么完全可以定义一个精度阈值:
类似:const double eps =1e-7; 然后最后一个 else 改为:else if ( fabs ((mid * mid) -num ) < eps ) 如果害怕面试官看不懂,在 eps 那一句再加上个注释就好了。 |
10
lewis89 OP @also24 #9 面试的时候 没想到过 一般都是做的整数查找 迭代的终止条件比较清楚 mid == target
小数当时没有意识到,尴尬了.. |
11
bitholic 2020-01-19 19:49:34 +08:00
面试官可能只是随便找了到 leetcode 原题而已,https://leetcode.com/problems/sqrtx/
|
12
zhgg0 2020-01-19 19:54:55 +08:00
你这写法最终得到的结果差太远了吧,不考虑小数位,得到的整数位都不对。
|
13
xuanbg 2020-01-19 20:15:17 +08:00
楼主这个算法计算 2 的平方根要迭代多少次啊……而且算不准 4、9、16 这些数的平方根
|
14
misdake 2020-01-19 20:36:49 +08:00
mid 不再变化的时候,取 low 和 high 中误差较小的一个。
|
15
lhx2008 2020-01-19 20:46:20 +08:00
这个题本质是二分查找,二分查找不总是有等于号的情况的,可以参考 lower bound 的写法,或者一个简单的变式,找[0,0,0,0,1,1,1] 中 0 的个数,这个题其实 if 格式和平方根是一样的。
|
16
xupefei 2020-01-19 20:56:50 +08:00
你可以写 if(mid*mid >= num && (mid+1)*(mid+1) <= num) return mid 哇。
|
18
ihciah 2020-01-20 02:06:16 +08:00
impl Solution {
pub fn my_sqrt(x: i32) -> i32 { let mut low: i64 = 0; let mut high: i64 = x as i64; while low < high { let mid = low + (high - low + 1) / 2; if mid * mid > x as i64 { high = mid - 1; } else { low = mid; } } low as i32 } } 不是精确查找,if 两个分支就够了。 |
19
lewis89 OP @xupefei #16 当时没想过,实际上不一定要相等才能结束迭代,可以差值在一个范围内 break 出迭代 也能返回一个近似值
|
20
lewis89 OP @bitholic #11 并不是 上面要求的返回值是 double 类型,没要求 int 类型,double 类型的话 OJ 不太好判题
|
22
ebingtel 2020-01-20 08:43:54 +08:00
double mid = (low + high) / 2;……容易溢出的吧
|
23
ineed123 2020-01-20 10:04:26 +08:00
double mid = (high - low) / 2 + low; 或 double mid = low + ((high - low) >> 1); // 防止溢出
|
24
Jrue0011 2020-01-20 10:55:39 +08:00
看到楼主这帖子。。我这种大学数学全忘了的在网上搜了下,高数里有个二分法求方程根的近似值,别说还挺像的。。
|