diff options
| -rw-r--r-- | array.c | 83 | ||||
| -rw-r--r-- | doc/bsearch.rdoc | 120 | ||||
| -rw-r--r-- | range.c | 46 |
3 files changed, 123 insertions, 126 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 diff --git a/doc/bsearch.rdoc b/doc/bsearch.rdoc new file mode 100644 index 0000000000..ca8091fc0d --- /dev/null +++ b/doc/bsearch.rdoc @@ -0,0 +1,120 @@ +== Binary Searching + +A few Ruby methods support binary searching in a collection: + +Array#bsearch:: Returns an element selected via a binary search + as determined by a given block. +Array#bsearch_index:: Returns the index of an element selected via a binary search + as determined by a given block. +Range#bsearch:: Returns an element selected via a binary search + as determined by a given block. + +Each of these methods returns an enumerator if no block is given. + +Given a block, each of these methods returns an element (or element index) from +self+ +as determined by a binary search. +The search finds an element of +self+ which meets +the given condition in <tt>O(log n)</tt> operations, where +n+ is the count of elements. ++self+ should be sorted, but this is not checked. + +There are two search modes: + +Find-minimum mode:: method +bsearch+ returns the first element for which + the block returns +true+; + the block must return +true+ or +false+. +Find-any mode:: method +bsearch+ some element, if any, for which + the block returns zero. + the block must return a numeric value. + +The block should not mix the modes by sometimes returning +true+ or +false+ +and other times returning a numeric value, but this is not checked. + +<b>Find-Minimum Mode</b> + +In find-minimum mode, the block must return +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>. + +Less formally: the block is such that all +false+-evaluating elements +precede all +true+-evaluating elements. + +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 + + r = (0...a.size) + r.bsearch {|i| a[i] >= 4 } #=> 1 + r.bsearch {|i| a[i] >= 6 } #=> 2 + r.bsearch {|i| a[i] >= 8 } #=> 3 + r.bsearch {|i| a[i] >= 100 } #=> nil + r = (0.0...Float::INFINITY) + r.bsearch {|x| Math.log(x) >= 0 } #=> 1.0 + +These blocks make sense 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.map {|x| x == 7 } # => [false, false, true, false, false] + +<b>Find-Any Mode</b> + +In find-any mode, the block must return 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>. + +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. + +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 + + a = [0, 100, 100, 100, 200] + r = (0..4) + r.bsearch {|i| 100 - a[i] } #=> 1, 2 or 3 + r.bsearch {|i| 300 - a[i] } #=> nil + r.bsearch {|i| 50 - a[i] } #=> nil + +These blocks make sense 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.map {|element| element <=> 7 } # => [-1, -1, 0, 1, 1] @@ -662,52 +662,10 @@ bsearch_integer_range(VALUE beg, VALUE end, int excl) * call-seq: * rng.bsearch {|obj| block } -> value * - * By using binary search, finds a value in range which meets the given - * condition in O(log n) where n is the size of the range. + * Returns an element from +self+ selected by a binary search. * - * You can use this method in two use cases: a find-minimum mode and - * a find-any mode. In either case, the elements of the range must be - * monotone (or sorted) with respect to the block. + * See {Binary Searching}[doc/bsearch_rdoc.html]. * - * In find-minimum mode (this is a good choice for typical use case), - * the block must return true or false, and there must be a value x - * so that: - * - * - the block returns false for any value which is less than x, and - * - the block returns true for any value which is greater than or - * equal to x. - * - * If x is within the range, this method returns the value x. - * Otherwise, it returns nil. - * - * ary = [0, 4, 7, 10, 12] - * (0...ary.size).bsearch {|i| ary[i] >= 4 } #=> 1 - * (0...ary.size).bsearch {|i| ary[i] >= 6 } #=> 2 - * (0...ary.size).bsearch {|i| ary[i] >= 8 } #=> 3 - * (0...ary.size).bsearch {|i| ary[i] >= 100 } #=> nil - * - * (0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0 - * - * In find-any mode (this behaves like libc's bsearch(3)), the block - * must return a number, and there must be two values x and y (x <= y) - * so that: - * - * - the block returns a positive number for v if v < x, - * - the block returns zero for v if x <= v < y, and - * - the block returns a negative number for v if y <= v. - * - * This method returns any value which is within the intersection of - * the given range and x...y (if any). If there is no value that - * satisfies the condition, it returns nil. - * - * ary = [0, 100, 100, 100, 200] - * (0..4).bsearch {|i| 100 - ary[i] } #=> 1, 2 or 3 - * (0..4).bsearch {|i| 300 - ary[i] } #=> nil - * (0..4).bsearch {|i| 50 - ary[i] } #=> nil - * - * You must not mix the two modes at a time; the block must always - * return either true/false, or always return a number. It is - * undefined which value is actually picked up at each iteration. */ static VALUE |