19

我注意到，从 Ruby 2.0.0 开始，数组类有一个bsearch我正在测试的方法，但我没有得到我期望的行为。为什么它返回 2 和 5 而不是nil-1、1 和 4 的值？

arr_in = [-1, 1, 2, 4, 5]

arr_in.bsearch { |x| x == 3 }   #=> nil
arr_in.bsearch { |x| x == -1 }  #=> nil
arr_in.bsearch { |x| x == 1 }   #=> nil
arr_in.bsearch { |x| x == 2 }   #=> 2
arr_in.bsearch { |x| x == 4 }   #=> nil
arr_in.bsearch { |x| x == 5 }   #=> 5
4

2 回答 2

33 
arr_in = [-1, 1,2,4,5]
arr_in.bsearch{ |x| 2 - x }
#=> 2
arr_in.bsearch{ |x| -1 - x }
#=> -1
arr_in.bsearch{ |x| 3 - x }
#=> nil

二分搜索使用块的结果作为提示，应该选择数组的哪一部分（左侧或右侧）在下一次迭代中进行搜索。如果块返回 0，它将停止搜索。如果它返回小于 0，它将向左移动，否则向右移动 :)

更多信息在这里 http://www.ruby-doc.org/core-2.1.1/Array.html#method-i-bsearch

UPD

好的，我们举个例子

arr_in = [-1, 1, 2, 4, 5]
arr_in.bsearch { |x| x == 3 }

首先，我们将获取中间元素 (2) 并将其交给块。2 == 3将返回false，所以我们移动到数组的右侧。

我们取中间元素[4, 5]is5和5 == 3isfalse

右边没有任何元素，所以我们将返回nil

arr_in = [-1, 1, 2, 4, 5]
arr_in.bsearch { |x| x == 2 }

首先2 == 2是true。我们往左边走。

的中间元素[-1, 1]是 1.1 == 2是false. 我们向右走。

1 右边没有任何元素[-1, 1]，所以我们返回最后一个返回true语句的最后一个元素2

PS：不要忘记，数组应该排序；）

于 2014-04-22T14:20:42.320 回答
17

我发现使用宇宙飞船操作符更直观

array.bsearch {|x| 3 <=> x }

只需确保将 放在x飞船的右侧即可。

原因是每次迭代期间要比较的东西是左操作数。因此，如果你想找到一个 3，你需要不断地与一个 3 进行比较，以获得正确的左、右或相等的结果。如果你把变量放在左边（就像直觉上做的那样），你已经反转了比较输出，挫败了 bsearch 算法！

这也适用于字符串和任何与<=>.

于 2017-01-20T08:37:23.507 回答