这样的面试题是否有意义？

[lewis89]

一个算法题

要求用二分查找实现

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 相乘，在一定精度情况下居然能够得到一个整数， 当然我理解其中的原理，由于二进制长度限制，有限的位置不可能表示无限精度的小数，所以其乘法运算可能会出现溢出的情况，然后乘法运算溢出后的结果刚刚是一个整数。

标题党 仅供讨论， 没有任何贬低这个题的意思，主要我面试的时候当时也没考虑到
这种二分迭代终止的方式，面试完了 才想起来。

当然毫无疑问的挂了.. 有去面 tuhu 的 可能用得上，算是小小的泄题了..

[yuankui]

面试官正在为自己想到这么优秀的解法而骄傲

[lewis89]

@yuankui #1 这个解法是我事后想到的，出题的事后 他也没讲精度，没有精度约束的话 只能这样求解，但是我又不敢这样写。

[RtIHZ]

```
const double DELTA = 0.000001;
if (abs(mid * mid - num) < DELTA) {
// ...
}
```

[InkStone]

我觉得你想多了，面试官可能单纯是想让你用牛顿法……

[RtIHZ]

这题我觉得出的没毛病。

[InkStone]

或者就像三楼那么写二分，完全没有问题。楼主你事后想出来的这个写法有 UB，肯定不能这么写的……

[lewis89]

@InkStone #4 指明了要用二分法..

[lewis89]

@InkStone #6 我知道 3 楼那个写法也是一个选择..

[also24]

既然你已经意识到了精度问题，那么完全可以定义一个精度阈值：

类似：const double eps =1e-7;

然后最后一个 else 改为：else if ( fabs ((mid * mid) -num ) < eps )

如果害怕面试官看不懂，在 eps 那一句再加上个注释就好了。

[lewis89]

@also24 #9 面试的时候 没想到过 一般都是做的整数查找 迭代的终止条件比较清楚 mid == target
小数当时没有意识到，尴尬了..

[bitholic]

面试官可能只是随便找了到 leetcode 原题而已，https://leetcode.com/problems/sqrtx/

[zhgg0]

你这写法最终得到的结果差太远了吧，不考虑小数位，得到的整数位都不对。

[xuanbg]

楼主这个算法计算 2 的平方根要迭代多少次啊……而且算不准 4、9、16 这些数的平方根

[misdake]

mid 不再变化的时候，取 low 和 high 中误差较小的一个。

[lhx2008]

这个题本质是二分查找，二分查找不总是有等于号的情况的，可以参考 lower bound 的写法，或者一个简单的变式，找[0,0,0,0,1,1,1] 中 0 的个数，这个题其实 if 格式和平方根是一样的。

[xupefei]

你可以写 if(mid*mid >= num && (mid+1)*(mid+1) <= num) return mid 哇。

[lewis89]

@xuanbg #13 你运行一下试试 可以算准的，对于没法直接整数的 可能有误差

[ihciah]

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 两个分支就够了。

[lewis89]

@xupefei #16 当时没想过，实际上不一定要相等才能结束迭代，可以差值在一个范围内 break 出迭代 也能返回一个近似值

[lewis89]

@bitholic #11 并不是 上面要求的返回值是 double 类型，没要求 int 类型，double 类型的话 OJ 不太好判题

[lewis89]

@bitholic #11 如果是 int 型的话 我可能就已经想出来了

[ebingtel]

double mid = (low + high) / 2;……容易溢出的吧

[ineed123]

double mid = (high - low) / 2 + low; 或 double mid = low + ((high - low) >> 1); // 防止溢出

[Jrue0011]

看到楼主这帖子。。我这种大学数学全忘了的在网上搜了下，高数里有个二分法求方程根的近似值，别说还挺像的。。