Ruby 2.0.0 Array#bsearch behavior

Question

I noticed that as of Ruby 2.0.0 the array class has a bsearch method that I was testing and I'm not getting the behavior I'd expect. Why does it return a value for 2 and 5 but nil for -1, 1, and 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

Binary search uses block's result as a hint which part of array (left or right side) should be chosen for searching on next iteration. If block returns 0 it will stop searching. If it returns less then 0 it will go left otherwise it goes right :)

More information here http://www.ruby-doc.org/core-2.1.1/Array.html#method-i-bsearch

UPD

Ok, let's take your example

arr_in = [-1, 1, 2, 4, 5]
arr_in.bsearch { |x| x == 3 }

First we will take middle element (2) and yield it to the block. 2 == 3 will return false, so we move to the right side of the array.

We take middle element of [4, 5] which is 5 and 5 == 3 is false

There is no any elements on the right, so we will return nil

arr_in = [-1, 1, 2, 4, 5]
arr_in.bsearch { |x| x == 2 }

First 2 == 2 is true. We go to the left.

Middle element of [-1, 1] is 1. 1 == 2 is false. We go to the right.

There is no any elements in [-1, 1] right to the 1, so we return last last element which returned true statement which is 2

PS: don't forget, that the array should be sorted ;)

Answer 2

I find it more intuitive to use the spaceship operator

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

Just make sure to put the x to the right of the spaceship.

The reason why is that the thing being compared against during each iteration is the left-hand operand. So if you want to find a 3, you need to continually compare against a 3, in order to get the correct left, right, or equal result. If you put the variable on the left (as one might intuitively to do), you've reversed the comparison output, foiling the bsearch algorithm!

This also works for strings and any object that is comparable with <=>.