Issue #4766 has been updated by Eric Hodel.


No, it's not about finding any minimum value, it's about binary search:

> I propose Range#bsearch for binary search

and

> Returns [กฤ] by binary search

The important information in English does not necessarily come first.  To make it more clear maybe it should read:

> Performs a binary search using the block as criteria.  If multiple items match the criteria the minimum (first) value is chosen.

You do know what a "binary search" is, right?

http://en.wikipedia.org/wiki/Binary_search

When performing a binary search you may have multiple matching values, the three 100 values from the example.  For the proposed implementation the first one is chosen for consistency.

Nobody knows what the #beach method you keep talking about would be.  Maybe you mean binary-search-each?  That doesn't make any sense as binary search will not yield each item in the enumerator.  If you think that this method will yield each item please read about binary search first.

----------------------------------------
Feature #4766: Range#bsearch
http://redmine.ruby-lang.org/issues/4766

Author: Yusuke Endoh
Status: Assigned
Priority: Normal
Assignee: Yusuke Endoh
Category: 
Target version: 1.9.x


Hello,

I propose Range#bsearch for binary search:

  ary = [0, 4, 7, 10, 12]
  p (0..4).bserach {|i| ary[i] >= 4 } #=> 1
  p (0..4).bserach {|i| ary[i] >= 6 } #=> 2

  p (0.0...Float::INFINITY).bsearch {|x| Math.log(x) >= 0 } #=> 1.0


Rdoc:

 *  call-seq:
 *     rng.bsearch {|obj| block }  -> element
 *
 *  Returns the minimum value in range which meets the block by binary search.
 *  The block must be monotone for arguments; in other words, it must have any
 *  following properties:
 *
 *    - there is a value so that the block returns false for any smaller value
 *      than the value, and that the block returns true for any bigger (or
 *      equal) value than the value,
 *    - the block always return true, or
 *    - the block always return false.
 *
 *  If the block is not monotone, the behavior is not unspecified.
 *
 *  Returns nil when there is no value that meets the block..
 *
 *
 *     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
 *
 *
 *  Note that this method does not stop search immediately when the block
 *  returns true.  This is because this method find the *minimum* value:
 *
 *     ary = [0, 100, 100, 100, 200]
 *     (0..4).bsearch {|i| p ary[i]; ary[i] >= 100 }
 *       # may output "100" more than once



Discussion:

You might think Array#bsearch is better.  But Array#bsearch has some problems:

  - Binary search is usable for not only an array but also a function.
    (See the above example for Math.log)
    Nevertheless, Array#bsearch can be used only for an array.
    Range#bsearch covers both.  You can use it for an array as follows:

      ary.sort!
      i = (0...ary.size).bsearch {|i| condition(ary[i]) }
      p ary[i]

  - matz hated Array#bsearch because its precondition (Array must be sorted)
    seems too strong (to him).  [ruby-dev:17125]
    Range#bsearch has the same precondition in effect (the block must be
    monotone), but there is a difference that this condition is for "code",
    not "state".  In fact, Array#sort has a similar condition.


I think there is demand for this feature because similar feature requests
are often proposed: [ruby-dev:17122] [ruby-core:30892] [ruby-dev:38545]

More importantly, this feature is often required in many programming
contests :-)


A patch is attached.  Thank you for your consideration.

-- 
Yusuke Endoh <mame / tsg.ne.jp>


-- 
http://redmine.ruby-lang.org