Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Ruby 2.0.0 Array#bsearch behavior

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
like image 223
jshort Avatar asked Apr 22 '14 14:04

jshort


People also ask

Does Ruby have arrays?

Introduction. An array is a data structure that represents a list of values, called elements. Arrays let you store multiple values in a single variable. In Ruby, arrays can contain any data type, including numbers, strings, and other Ruby objects.

What is array Ruby?

Ruby arrays are ordered, integer-indexed collections of any object. Each element in an array is associated with and referred to by an index. Array indexing starts at 0, as in C or Java.


2 Answers

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

like image 142
fl00r Avatar answered Nov 16 '22 01:11

fl00r


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

like image 25
akuhn Avatar answered Nov 15 '22 23:11

akuhn