19

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
alk
  • 69,737
  • 10
  • 105
  • 255
jshort
  • 1,006
  • 8
  • 23

2 Answers2

34
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 ;)

fl00r
  • 82,987
  • 33
  • 217
  • 237
  • You should explain what happened *in find-minimum mode* ? As OP's examples is related to this. – Arup Rakshit Apr 22 '14 at 14:24
  • @ArupRakshit I though author is asking about find-any, doesn't he? – fl00r Apr 22 '14 at 14:28
  • So the find-any syntax in this post works. I guess my boolean expression in the find-minimum mode is incorrect since it is testing equality and not >=. Anyway, the behavior is still unclear to me in my above snippet even after reading the documentation. Basically I just want a binary search that returns the value being searched for if found and nil otherwise. – jshort Apr 22 '14 at 14:35
  • @jshort, I've updated my answer. If your block returns Boolean value it will be executed as find-minimum, while if you return a Number it will be executed as find any. – fl00r Apr 22 '14 at 19:09
  • 3
    So if you need to implement same functionality as `Array#detect` you need to use `array.bsearch{ |x| MYVAL - x }` – fl00r Apr 22 '14 at 19:09
  • That was a great explanation, thanks so much! Just wrote a wrapper to this method to make it behave a little bit more like a traditional bsearch method. – jshort Apr 23 '14 at 16:45
  • @fl00r your comment should be an answer! (and please also mention that the array should be sorted ;) If you don't put it put, I'll happily make it an answer. – Overbryd Apr 27 '16 at 08:35
18

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

akuhn
  • 27,477
  • 2
  • 76
  • 91
  • 4
    This should be the accepted answer. Then there's no need to write "a wrapper to this method" imo. Also, I think it'd be worthwhile to explain why you say, "make sure to put the `x` to the right of the spaceship operator `<=>` ... 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 intuit to do), you've reversed the comparison output, foiling the bsearch algo! – likethesky Aug 11 '19 at 02:05