为什么这个 Ruby 二进制搜索代码不起作用？
我有这样的代码
def search(begins, ends)
puts "Searching for #{begins}- #{ends}"
temp = ((begins + ends) / 2).to_i
if is_valid? temp
if (ends - begins).abs < 3 # the result is between a and 2 digits than b
return temp # recursion ends
else
search(begins, temp)
end
else
search(temp, ends)
end
end
0 到 10000000 之间的数字范围通过 is_valid 函数。我想找到使用此代码传递此函数的第一个和最后一个元素，但它不起作用，甚至不接近。它进入无限循环，这里有几行输出
Searching for 0- 14981245
Searching for 0- 7490622
Searching for 3745311- 7490622
Searching for 3745311- 5617966 # good result
Searching for 3745311- 4681638
Searching for 3745311- 4213474
Searching for 3745311- 3979392
Searching for 3745311- 3862351
Searching for 3745311- 3803831
Searching for 3745311- 3774571
Searching for 3759941- 3774571
Searching for 3759941- 3767256
Searching for 3759941- 3763598
Searching for 3759941- 3761769
Searching for 3759941- 3760855
Searching for 3760398- 3760855
Searching for 3760626- 3760855
I have code like this
def search(begins, ends)
puts "Searching for #{begins}- #{ends}"
temp = ((begins + ends) / 2).to_i
if is_valid? temp
if (ends - begins).abs < 3 # the result is between a and 2 digits than b
return temp # recursion ends
else
search(begins, temp)
end
else
search(temp, ends)
end
end
There is a range of numbers between 0 and 10000000 that pass is_valid function. I want to find first and last element that pass this function using this code but it doesn't work it isn't even close.It go in endless loop and here are few lines of output
Searching for 0- 14981245
Searching for 0- 7490622
Searching for 3745311- 7490622
Searching for 3745311- 5617966 # good result
Searching for 3745311- 4681638
Searching for 3745311- 4213474
Searching for 3745311- 3979392
Searching for 3745311- 3862351
Searching for 3745311- 3803831
Searching for 3745311- 3774571
Searching for 3759941- 3774571
Searching for 3759941- 3767256
Searching for 3759941- 3763598
Searching for 3759941- 3761769
Searching for 3759941- 3760855
Searching for 3760398- 3760855
Searching for 3760626- 3760855
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
查看您编写的代码：其中没有任何内容会导致
ends在您声明的点处接近 3745311。 3745311 + 7490622 是 11235933，除以 2 得到 5617966，就像你看到的那样。 5617966 - 3745311 远大于 3，因此它会计算出 3745311 + 5617966，即 4681638，正如您所看到的那样。我想也许您想使用
ends / 2而不是(begins +ends) / 2。这将导致它在您期望的位置处变为 3745311。Look at the code you've written: Nothing in it would cause
endsto be anywhere near 3745311 at the point you claim. 3745311 + 7490622 is 11235933, which divided by 2 gives us 5617966 just like you're seeing. 5617966 - 3745311 is much greater than 3, so it then calculates 3745311 + 5617966, which is 4681638 — again, just as you're seeing.I think maybe you wanted to use
ends / 2rather than(begins + ends) / 2. That would cause it to be 3745311 at the point you're expecting.