破解密码本的平方根算法中的整数范围

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

因为您提到“破解编码面试” ...

[通常，在一般的编码采访中，人们不会担心这样的实现特定细节。面试官正在尝试确认基本的能力和理解力-他们很少想要运行您的代码，并且应该为您双方提供一种算法，该算法将在您的语言基本数据类型的极限范围内崩溃。如果访问者专门询问限制问题，那么您可以简短地提及该函数对于使用该语言的值大于（Integer.MAX_VALUE / 2）的情况将失败。

该限制将几乎适用于您为编码面试编写的所有算法，并且没有任何合理的面试官会期望您专门设计解决方案来缓解这种情况。如果我要求应聘者编写一个产生斐波那契数的函数，而他们花时间尝试优化输出超过16位数字的情况，我会觉得很不对劲。

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

Answer 2

您必须确认您的语言。但是您可以使用伪代码执行类似的操作：

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

Answer 3

有解决此问题的简单方法（例如min + (max - min) / 2。

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

[如果您能够提供Newton-Raphson algorithm，会非常迅速地给采访员留下深刻的印象。