一个算法题
要求用二分查找实现
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 年 1 月 19 日
面试官正在为自己想到这么优秀的解法而骄傲
|
3
RtIHZ 2020 年 1 月 19 日 ```
const double DELTA = 0.000001; if (abs(mid * mid - num) < DELTA) { // ... } ``` |
4
InkStone 2020 年 1 月 19 日
我觉得你想多了,面试官可能单纯是想让你用牛顿法……
|
5
RtIHZ 2020 年 1 月 19 日
这题我觉得出的没毛病。
|
6
InkStone 2020 年 1 月 19 日
或者就像三楼那么写二分,完全没有问题。楼主你事后想出来的这个写法有 UB,肯定不能这么写的……
|
9
also24 2020 年 1 月 19 日
既然你已经意识到了精度问题,那么完全可以定义一个精度阈值:
类似:const double eps =1e-7; 然后最后一个 else 改为:else if ( fabs ((mid * mid) -num ) < eps ) 如果害怕面试官看不懂,在 eps 那一句再加上个注释就好了。 |
10
lewis89 OP @also24 #9 面试的时候 没想到过 一般都是做的整数查找 迭代的终止条件比较清楚 mid == target
小数当时没有意识到,尴尬了.. |
11
bitholic 2020 年 1 月 19 日
面试官可能只是随便找了到 leetcode 原题而已,https://leetcode.com/problems/sqrtx/
|
12
zhgg0 2020 年 1 月 19 日
你这写法最终得到的结果差太远了吧,不考虑小数位,得到的整数位都不对。
|
13
xuanbg 2020 年 1 月 19 日
楼主这个算法计算 2 的平方根要迭代多少次啊……而且算不准 4、9、16 这些数的平方根
|
14
misdake 2020 年 1 月 19 日
mid 不再变化的时候,取 low 和 high 中误差较小的一个。
|
15
lhx2008 2020 年 1 月 19 日
这个题本质是二分查找,二分查找不总是有等于号的情况的,可以参考 lower bound 的写法,或者一个简单的变式,找[0,0,0,0,1,1,1] 中 0 的个数,这个题其实 if 格式和平方根是一样的。
|
16
xupefei 2020 年 1 月 19 日
你可以写 if(mid*mid >= num && (mid+1)*(mid+1) <= num) return mid 哇。
|
18
ihciah 2020 年 1 月 20 日
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 两个分支就够了。 |
22
ebingtel 2020 年 1 月 20 日
double mid = (low + high) / 2;……容易溢出的吧
|
23
ineed123 2020 年 1 月 20 日
double mid = (high - low) / 2 + low; 或 double mid = low + ((high - low) >> 1); // 防止溢出
|
24
Jrue0011 2020 年 1 月 20 日
看到楼主这帖子。。我这种大学数学全忘了的在网上搜了下,高数里有个二分法求方程根的近似值,别说还挺像的。。
|