使用二进制搜索在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片段中