Ruby: bsearch返回零

Question

我有一个排序的数字数组，并希望检查数字是否在数组中。我认为这里应该使用bsearch，但是即使数组中有数字，它也会返回nil，并且只给出中间元素的正结果。

这是我要测试的。

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

我正在使用RubyVersion2.3.8

Answer 1

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

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

• 所有正评价元素先于所有零评估元素，
• 所有正评价元素先于所有负面评估元素，
• 所有零评估元素先于所有负面评估元素。

。

您的块违反了这些要求。

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

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

让我们再看一下文档：

在查找-任意模式下作为块都是有意义的：

A= 0，4，7，10，12 a.map {AC.26元素7 <=>元素}# => 1，1，0，-1，-1 a.map {AC.26 element { <=> element }# => -1，-1，-1，-1，-1，-1，-1 a.map {AC.26 element 5 <=> element }# => 1，1，- 1，- 1，- 1，- 1，-1 a.map {element 15 <=> element}# => 1，1，1，1，1，-1

这是没有道理的：

A= 0，4，7，10，12 a.map {区元素<=> 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