使用二进制搜索在C中查找数字的平方根

试图使用二进制搜索计算出数字的平方根,但是我的实现不起作用,我不知道为什么 – 任何帮助表示赞赏,谢谢

inheritance我的代码。 ‘end’是我希望平方根的数字的值

while(start <= end) { float mid = ((start + end) / 2); printf("\nhalving mid"); if(mid * mid == end){ sqrt = mid; printf("\nsqrt = %d", sqrt); } if(mid * mid < end){ start = mid + 1; sqrt = mid; printf("\nsqrt: %d", sqrt); } else{ start = mid - 1; } } 

除了代码中的逻辑问题之外,比较浮点数也不是一个好习惯。

mid * mid == end可能总是会失败,即使对于sqrt(9)也是如此,因为测试浮点数是非常困难的 。

使用范围(epsil)而不是比较来查看此实现:

 static float my_sqrt(float num) { double start = 0.0; double end = num; double sqrt = 0.0; double epsil = 0.000001; while (start <= end) { double mid = ((start + end) / 2); sqrt = mid; printf("sqrt = %f\n", sqrt); if (fabs(mid * mid -num) <= epsil) { break; } else if (mid * mid < num) { start = mid; } else { end = mid; } } return sqrt; } 

我没有修复你的代码,只是解释我将如何写它。

使用表示解决方案包围的不变量:

 low² <= N < high² 

然后取中间值,测试

 mid² <= N 

允许选择

 low² <= N < mid² and mid² <= N < high² 

并缩小搜索间隔。

当搜索间隔很小时,迭代可以停止,因为浮点表示允许(即单个精度为23位)。 你可以在low == high时停止。

建立不变量,

 low= 0, high= N 

如果0 <= N < N² ,则可以这样做。 当N <= 1时,这不起作用。 快速而肮脏的解决方法是设置high= 1

 low= 0 if N >= 1: high= N else: high= 1 while low < high: mid= 0.5 * (low + high) if mid * mid <= N: high= mid else: low= mid 

IMO,测试等于mid² == N ,然后不等式mid² < N适得其反。 当N是一个完美的正方形时,您可能会认为提前终止可以缩短执行时间。 但实际上,大多数输入数字都不是完美的正方形,你将进行两次测试而不是一次,这使得程序平均变慢。

当然最后一行应该是

  end = mid - 1; 

符合这三个案例

 start..mid-1, mid, mid+1..end 

并且您应该分隔要计算搜索间隔的平方根和结束的数字num


当然,当平方根不是整数时,你也会遇到问题。 然后在某个时刻它将落入其中一个区间(mid-1, mid)(mid, mid+1) ,因此在算法之外。

因此,您需要将案例分开

 [start, mid] (mid, mid+1), [mid+1,end] 

如果你想保持整数边界。 中间案例是

  ( mid*mid> num ) && ( (mid+1)*(mid+1) < num ) 
 public int sqrt(int x) { if (x == 0) return 0; int left = 1, right = Integer.MAX_VALUE; while (true) { int mid = left + (right - left)/2; if (mid > x/mid) { right = mid - 1; } else { if (mid + 1 > x/(mid + 1)) return mid; left = mid + 1; } } } 

你应该用你的最后一行替换

 end = mid -1 

在else片段中