End of Life Ruby 3.0 has reached end of life and gets no more fixes. Switch to Ruby 4.0 →

instance method

Array#bsearch

array.bsearch {|element| ... } → object

array.bsearch → new_enumerator

static VALUE
rb_ary_bsearch(VALUE ary)
{
    VALUE index_result = rb_ary_bsearch_index(ary);

    if (FIXNUM_P(index_result)) {
        return rb_ary_entry(ary, FIX2LONG(index_result));
    }
    return index_result;
}

Returns an element from self selected by a binary search. self should be sorted, but this is not checked.

By using binary search, finds a value from this array which meets the given condition in O(log n) where n is the size of the array.

There are two search modes:

Find-minimum mode: the block should return true or false.
Find-any mode: the block should return a numeric value.

The block should not mix the modes by and sometimes returning true or false and sometimes returning a numeric value, but this is not checked.

Find-Minimum Mode

In find-minimum mode, the block always returns true or false. The further requirement (though not checked) is that there are no indexes i and j such that:

0 <= i < j <= self.size.
The block returns true for self[i] and false for self[j].

In find-minimum mode, method bsearch returns the first element for which the block returns true.

Examples:

Example

a = [0, 4, 7, 10, 12]
a.bsearch {|x| x >= 4 } # => 4
a.bsearch {|x| x >= 6 } # => 7
a.bsearch {|x| x >= -1 } # => 0
a.bsearch {|x| x >= 100 } # => nil

Less formally: the block is such that all false-evaluating elements precede all true-evaluating elements.

These make sense as blocks in find-minimum mode:

Example

a = [0, 4, 7, 10, 12]
a.map {|x| x >= 4 } # => [false, true, true, true, true]
a.map {|x| x >= 6 } # => [false, false, true, true, true]
a.map {|x| x >= -1 } # => [true, true, true, true, true]
a.map {|x| x >= 100 } # => [false, false, false, false, false]

This would not make sense:

Example

a = [0, 4, 7, 10, 12]
a.map {|x| x == 7 } # => [false, false, true, false, false]

Find-Any Mode

In find-any mode, the block always returns a numeric value. The further requirement (though not checked) is that there are no indexes i and j such that:

0 <= i < j <= self.size.
The block returns a negative value for self[i] and a positive value for self[j].
The block returns a negative value for self[i] and zero self[j].
The block returns zero for self[i] and a positive value for self[j].

In find-any mode, method bsearch returns some element for which the block returns zero, or nil if no such element is found.

Examples:

Example

a = [0, 4, 7, 10, 12]
a.bsearch {|element| 7 <=> element } # => 7
a.bsearch {|element| -1 <=> element } # => nil
a.bsearch {|element| 5 <=> element } # => nil
a.bsearch {|element| 15 <=> element } # => nil

Less formally: the block is such that:

All positive-evaluating elements precede all zero-evaluating elements.
All positive-evaluating elements precede all negative-evaluating elements.
All zero-evaluating elements precede all negative-evaluating elements.

These make sense as blocks in find-any mode:

Example

a = [0, 4, 7, 10, 12]
a.map {|element| 7 <=> element } # => [1, 1, 0, -1, -1]
a.map {|element| -1 <=> element } # => [-1, -1, -1, -1, -1]
a.map {|element| 5 <=> element } # => [1, 1, -1, -1, -1]
a.map {|element| 15 <=> element } # => [1, 1, 1, 1, 1]

This would not make sense:

Example

a = [0, 4, 7, 10, 12]
a.map {|element| element <=> 7 } # => [-1, -1, 0, 1, 1]

Returns an enumerator if no block given:

Example

a = [0, 4, 7, 10, 12]
a.bsearch # => #<Enumerator: [0, 4, 7, 10, 12]:bsearch>

See also #at #bsearch_index #assoc #clear also in 4.1 · 4.0 · 3.4 · 3.3 · 3.2 · 3.1

‹ prev#at next ›#bsearch_index