时间戳

首页 > 解决方案 > 破解密码书平方根算法中的整数范围

java - 破解密码书平方根算法中的整数范围

问题描述

破解密码本的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也可以。

标签： javaalgorithminteger-overflowsquare-root

解决方案

既然你提到了“破解编码面试”......

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

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

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

推荐阅读