Any way to get bsearch to consistently do equality matching?

Question

As with the sample array from the docs, passing an equality returns inconsistent results:

[0, 4, 7, 10, 12].bsearch{ |x| x == 4}  # => nil
[0, 4, 7, 10, 12].bsearch{ |x| x == 7}  # => 7
[0, 4, 7, 10, 12].bsearch{ |x| x == 10} # => nil
[0, 4, 7, 10, 12].bsearch{ |x| x == 12} # => 12
[0, 4, 7, 10, 12].bsearch{ |x| x == 0}  # => nil

As the docs show, you can get the correct result with >=; however you also get:

[0, 4, 7, 10, 12].bsearch {|x| x >= 6 } #=> 7

which is not what you want when you're looking specifically for 6. How do you get it to return consistent results?

Answer 1

According to the docs, to use bsearch, your array must be sorted with respect to the block.

Looking at your block results mapped out, [false, false, true, false, false] is not sorted.

Your block is currently set up to use find-minimum mode, because it returns true/false. Instead, try using find-any mode, with a block that returns -1/0/1.

[0, 4, 7, 10, 12].bsearch {|x| 7 <=> x } # => 7
[0, 4, 7, 10, 12].bsearch {|x| 6 <=> x } # => nil

In this case, we use the "comparator" or "spaceship" operator (<=>), which returns -1/0/1.