diff options
Diffstat (limited to 'array.c')
| -rw-r--r-- | array.c | 83 |
1 files changed, 1 insertions, 82 deletions
@@ -3422,89 +3422,8 @@ static VALUE rb_ary_bsearch_index(VALUE ary); * array.bsearch -> new_enumerator * * 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 <tt>O(log n)</tt> where +n+ is the size of the array. - * - * There are two search modes: - * - <b>Find-minimum mode</b>: the block should return +true+ or +false+. - * - <b>Find-any mode</b>: 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. - * - * <b>Find-Minimum Mode</b> - * - * 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: - * - <tt>0 <= i < j <= self.size</tt>. - * - The block returns +true+ for <tt>self[i]</tt> and +false+ for <tt>self[j]</tt>. - * - * In find-minimum mode, method bsearch returns the first element for which the block returns true. - * - * Examples: - * 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: - * 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: - * a = [0, 4, 7, 10, 12] - * a.map {|x| x == 7 } # => [false, false, true, false, false] - * - * <b>Find-Any Mode</b> - * - * 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: - * - <tt>0 <= i < j <= self.size</tt>. - * - The block returns a negative value for <tt>self[i]</tt> - * and a positive value for <tt>self[j]</tt>. - * - The block returns a negative value for <tt>self[i]</tt> and zero <tt>self[j]</tt>. - * - The block returns zero for <tt>self[i]</tt> and a positive value for <tt>self[j]</tt>. - * - * In find-any mode, method bsearch returns some element - * for which the block returns zero, or +nil+ if no such element is found. - * - * Examples: - * 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: - * 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: - * a = [0, 4, 7, 10, 12] - * a.map {|element| element <=> 7 } # => [-1, -1, 0, 1, 1] - * - * Returns an enumerator if no block given: - * a = [0, 4, 7, 10, 12] - * a.bsearch # => #<Enumerator: [0, 4, 7, 10, 12]:bsearch> + * See {Binary Searching}[doc/bsearch_rdoc.html]. */ static VALUE |