arraysrubybinary-searchbsearch

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