Ruby2.0.0 Array#bsearch行为

Question

我注意到，在Ruby2.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

Answer 1

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]的中间元素5和5 == 3是false

右边没有任何元素，所以我们将返回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:别忘了，数组应该排序;)

Answer 2

我发现使用太空船运算符更直观

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

一定要把x放在飞船的右边。

原因是在每次迭代中被比较的东西是左边的操作数。因此，如果您想要找到一个3，您需要不断地比较与一个3，以获得正确的左，右，或相等的结果。如果您将变量放在左边(您可能会直观地这样做)，那么您已经反转了比较输出，从而挫败了bsearch算法！

这也适用于字符串和与<=>类似的任何对象。