summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--array.c83
-rw-r--r--doc/bsearch.rdoc120
-rw-r--r--range.c46
3 files changed, 123 insertions, 126 deletions
diff --git a/array.c b/array.c
index 20ed9707133..d3eb7ce6d2d 100644
--- a/array.c
+++ b/array.c
@@ -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 00000000000..ca8091fc0da
--- /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]
diff --git a/range.c b/range.c
index 140abc36b4f..9dd2d4e942b 100644
--- a/range.c
+++ b/range.c
@@ -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