Cracking the Code book 平方根算法中的整数范围

Question

破解密码本java中有求平方根的算法如下：

int sqrt(int n) {
  return sqrt_helper(n, 1, n);
}

int sqrt_helper(int n, int min, int max) {
  if (max < min) return -1; 
  int guess = (min + max) / 2·,
  if (guess *guess == n) { 
    return guess;
  } else if (guess * guess < n) { 
    return sqrt_helper(n, guess + 1, max); 
  } else {  
    return sqrt_helper(n, min, guess - l); 
  }
}

问题是：

由于min和max是整数，它们可以是范围内的任何值，即max = Integer.MAX_VALUE

所以不用担心 guess = (min + max) / 2 因为它会超过允许的范围，或者 guess *guess 也会。

Answer 1

您必须确认您的语言。但是在伪代码中你可以做这样的事情：

int guess = ((min.ToBigInt() + max.ToBigInt()) / 2).ToInt()

Answer 2

既然你提到了"Cracking the Coding Interview"...

通常在普通编码面试的背景下，人们不会担心像这样的特定于实现的细节。面试官试图确认基本能力和理解力——他们很少想运行你的代码，你们俩都应该知道算法会在你的语言的基本数据的极限下崩溃类型。如果面试官特别询问有关限制的问题，那么您可以简单地提及该函数在这种语言中对于高于 (Integer.MAX_VALUE / 2) 的值会失败。

该限制将适用于您为编码面试编写的几乎所有算法，并且任何合理的面试官都不会期望您专门设计解决方案来缓解这种边缘情况。如果我要求候选人编写一个生成斐波那契数的函数并且他们花时间尝试优化输出超过 16 位值的情况，我会发现它非常令人反感。

如果出于某种原因您需要在现实生活场景中使用此算法求极大值的平方根，我希望您必须针对您的特定情况使用通用大数库来实现它语。话虽这么说，但在几乎任何情况下，我都不会针对任何实际用例推出自己的平方根算法。

Answer 3

有一些简单的方法可以解决这个问题（例如 min + (max - min) / 2）。

比较严重的整数溢出问题是guess * guess。您可以更改测试以将 guess 与 n / guess 进行比较，后者速度较慢但通常不会溢出。或者你可以使用一些 hack 来找到一个更好的起点（clz 在这里很有用，如果你有的话），因为你应该能够找到一个猜测，其平方在可表示整数的范围内。

如果您能够提供收敛速度极快的 Newton-Raphson algorithm，面试官可能会给面试官留下更深刻的印象。

Cracking the Code book 平方根算法中的整数范围

Integer range in square root algorithm of Cracking the Code book

java

algorithm

integer-overflow

square-root