Strange behavior with bsearch_index

Question

tmp = [-3,3,5]
p "test: #{tmp.bsearch_index{|j| j == -3}}"

In the above code, I get response as nil. If I compare j against 3, or 5, it works. Why does bsearch_index does not consider very first element?

Answer 1

You need to write

tmp.bsearch_index{|n| n >= -3}    #=> 0

This uses Array#bsearch_index's find minimum mode, which returns the smallest value in the array that satisfies the expression in the block. For example,

tmp.bsearch { |n| n >= 0 }        #=> 3
tmp.bsearch_index { |n| n >= 0 }  #=> 1

In this mode, to quote the doc for Array#bsearch, "the block must always return true or false, and there must be an index i (0 <= i <= ary.size) so that the block returns false for any element whose index is less than i, and the block returns true for any element whose index is greater than or equal to i. This method returns the i-th element. If i is equal to ary.size, it returns nil."

If the block were { |n| n == -3 } there would be no index i, 0 <= i <= tmp.size #=> 3 that has the property that tmp[j] == -3 is false for all j < i and true for all j >= 1.

If the block calculation were tmp[j] == 5 the requirement would be satisfied (for index 2) so the correct value would be returned. If the block calculation were tmp[j] == 3 the requirement would not be satisfied (tmp[2] == 3 #=> false); the fact that the correct index is returned is only due to the way the method has been implemented. If

tmp = [-3, 3, 5, 6]

then nil is returned for n == 3 as well as for n == -3:

tmp.bsearch_index { |n| n == 3 }  #=> nil

bsearch has a second mode, find any mode. (See the doc for Array#bsearch for details.) In this case we might write one of the following:

tmp.bsearch_index { |n| -3 - n }  #=> 0   
tmp.bsearch_index { |n|  3 - n }  #=> 1
tmp.bsearch_index { |n|  5 - n }  #=> 2
tmp.bsearch_index { |n|  4 - n }  #=> nil

This mode would be useful here if nil were to be returned when no element in the array evaluates to zero in the block. In other contexts it has a multitude of uses.