rubybsearch

when bsearch matches first element in array with 2 values it returns nil. Why?

I don't understand why bsearch method returns nil, when array has 2 values.

arr = [1, 2]

arr.bsearch { |el| el < 2 }
Solution

  • bsearch doc

    You just need to read the doc for Array#bsearch carefully. It states that are two forms or modes of bsearch: "find-minimum mode and find-any mode. In either case, the elements of the array must be monotone (or sorted) with respect to the block." With find-minimum mode the block returns true or false; with find-any mode a value of the same class as the elements of the array is returned by the block. You are therefore using the find-minimum mode.

    Also from the doc, in find-minimum mode "there must be an index i, 0 <= i <= ary.size so that:

    This method returns the i-th element. If i is equal to ary.size, it returns nil."

    Examining your code

    Now lets examine your statement, modified slightly:

    arr = [1, 2, 3]
arr.bsearch { |el| el < 2 } #=> nil

    We wish to find an index 0, 1 or 2 that satisfies the requirements imposed by the use of bsearch.

    Suppose the index of interest were 0. As there are no indices less than zero, we test whether arr[1] < 2 and arr[2] < 2 (2 < 2 and 3 < 2) are both true. In fact both are false. The index 0 is therefore removed from consideration.

    Now suppose the index referred to in the doc were 1. We require that arr[0] < 2 be false, but it is true. So we can rule out index 1.

    For the index to equal 2 to we require both arr[0] < 2 and arr[1] < 2 to be false but in fact both are true.

    As there is no index that satisfies the requirement for using besearch nil is returned.

    Correcting your code

    It is evident that, for arr = [1, 2, 3], the expression must be written as follows.

    arr.bsearch { |el| el >= 2 }      #=> 2
arr.bsearch { |el| el > 2  }      #=> 3
arr.bsearch { |el| el > 0  }      #=> 1
arr.bsearch { |el| el > 3  }      #=> nil

    Other examples

    Here are some more examples where the array contains integers.

    ary = [2, 4, 6]

ary.bsearch { |el| el > -99 }     #=> 2
ary.bsearch { |el| el > 1 }       #=> 2
ary.bsearch { |el| el > 2 }       #=> 4
ary.bsearch { |el| el >= 2 }      #=> 2
ary.bsearch { |el| el >= 6 }      #=> 6
ary.bsearch { |el| el > 6 }       #=> nil

    The array can be non-increasing

    Note that the array need not be non-deceasing, only monotone, which means non-deceasing or non-increasing. Here is an example where the array is non-increasing (it is in fact strictly decreasing). The block calculation must of course be adjusting accordingly.

    ary = [6, 4, 2]

ary.bsearch { |el| el <= 7 }    #=> 6
ary.bsearch { |el| el <= 99}    #=> 6
ary.bsearch { |el| el < 5 }     #=> 4
ary.bsearch { |el| el <= 4 }    #=> 4
ary.bsearch { |el| el < 4 }     #=> 2
ary.bsearch { |el| el <= 2 }    #=> 2
ary.bsearch { |el| el < 2 }     #=> nil  
ary.bsearch { |el| el <= 1 }    #=> nil

    The array may contain non-numeric values

    The only requirement is that pairs of elements can be compared with the spaceship operator, <=>. a <=> b returns -1 if a < b, returns 0 if a == b and returns 1 if a > b.

    In the case of strings, for example, String#<=> is used by bsearch. Here are some examples.

    ary = ['brush', 'keep', 'task']

ary.bsearch { |s| s >= 'hi' }     #=> "keep"
ary.bsearch { |s| s >= 'align' }  #=> "brush"
ary.bsearch { |s| s >= 'mama' }   #=> "task"
ary.bsearch { |s| s >= 'tar' }    #=> "task"
ary.bsearch { |s| s >= 'tax' }    #=> "nil"