Ruby: bsearch 返回 nil

Question

我有一个排序的数字数组，想检查数字是否在数组中。我想我应该在这里使用 bsearch 但它 return nil 即使数字存在于数组中，并且只对中间元素给出肯定的结果。

这是我测试的。

>> [1,2,3,4,5].bsearch { |value| value <=> 1}
>> nil
>> [1,2,3,4,5].bsearch { |value| value <=> 3}
>> 3

我正在使用 Ruby 版本 2.3.8

Answer 1

您正在查找任意模式中使用Array#bsearch。

如文档所述，您的区块需要满足以下要求：

All positive-evaluating elements precede all zero-evaluating elements.

All positive-evaluating elements precede all negative-evaluating elements.

All zero-evaluating elements precede all negative-evaluating elements.

您的区块违反了这些要求。

让我们运行通过一个例子。在第一次迭代中，Array#bsearch 将选择中间元素，即 3 并将其传递给您的块。您的块 returns 1，这意味着您正在搜索的元素大于 3 因此必须是 right 当前元素。所以，Array#bsearch 丢弃了数组的左半部分，我们剩下 [4, 5]。现在，Array#bsearch 再次选择“中间”元素，即 4 并将其传递给您的块。您的块 returns 1，这是一个正数，因此意味着您要查找的元素大于 4，因此必须位于数组的右半部分。因此，Array#bsearch 再次丢弃了左半部分，我们只剩下 [5]。同样，Array#bsearch 将 5 传递给块，您的块 returns 1 这是一个正数，因此意味着我们需要向右看，除了我们已经在数组的末尾，因此我们可以得出结论，您要查找的元素不在数组中。

所以，基本上，您只是在告诉 Array#bsearch 看错地方。

我们再看看文档：

These make sense as blocks in find-any mode:

a = [0, 4, 7, 10, 12]
a.map {|element| 7 <=> element } # => [1, 1, 0, -1, -1]
a.map {|element| -1 <=> element } # => [-1, -1, -1, -1, -1]
a.map {|element| 5 <=> element } # => [1, 1, -1, -1, -1]
a.map {|element| 15 <=> element } # => [1, 1, 1, 1, 1]

This would not make sense:

a = [0, 4, 7, 10, 12]
a.map {|element| element <=> 7 } # => [-1, -1, 0, 1, 1]

所以，基本上你写的块完全就像文档明确所说的块错误，并且与文档告诉您的方法完全相反。

如果您翻转块中的两个操作数，使您的块看起来像文档中的示例所说的那样，它将起作用：

[1, 2, 3, 4, 5].bsearch { |value| 0 <=> value } #=> nil
[1, 2, 3, 4, 5].bsearch { |value| 1 <=> value } #=> 1
[1, 2, 3, 4, 5].bsearch { |value| 2 <=> value } #=> 2
[1, 2, 3, 4, 5].bsearch { |value| 3 <=> value } #=> 3
[1, 2, 3, 4, 5].bsearch { |value| 4 <=> value } #=> 4
[1, 2, 3, 4, 5].bsearch { |value| 5 <=> value } #=> 5
[1, 2, 3, 4, 5].bsearch { |value| 6 <=> value } #=> nil

Ruby: bsearch 返回 nil

Ruby: bsearch returning nil

ruby

binary-search

ruby-on-rails-4