Ruby: bsearch returning nil

Question

I have an sorted array of number, and wanted to check if number is in the array or not. I think I should use bsearch here but it return nil even if the number is present in the array, and only give positive result for the middle element.

Here is what I test.

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

I am using Ruby version 2.3.8

Answer 1

You are using Array#bsearch in Find-any mode.

As the documentation says, your block needs to satisfy the following requirements:

• 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.

Your block violates those requirements.

Let's run through an example. In the first iteration, Array#bsearch will pick the middle element, which is 3 and pass it to your block. Your block returns 1, which means that the element you are searching for is greater than 3 and thus must be to the right of the current element. So, Array#bsearch throws away the left half of the array, and we are left with [4, 5]. Now again, Array#bsearch picks the "middle" element, which is 4 and passes it to your block. Your block returns 1, which is a positive number and thus means that the element you are looking for is greater than 4 and thus must be in the right half of the array. So again, Array#bsearch throws away the left half and we are left with [5]. Same thing, Array#bsearch passes 5 to the block, your block returns 1 which is a positive number and thus means we need to look to the right, except we are already at the end of the array, and thus we can conclude that the element you are looking for is not in the array.

So, basically, you are just telling Array#bsearch to look in the wrong place.

Let's look again at the documentation:

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]

So, essentially you wrote your block exactly like the block that the documentation explicitly says is wrong, and exactly the opposite way of what the documentation tells you to.

If you flip the two operands in the block, so that your block looks like the example in the documentation says it should look, it will work:

[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