From: Thomas Sawyer <transfire@...>
Date: 2011-07-18T00:13:59+09:00
Subject: [ruby-core:38139] [Ruby 1.9 - Feature #4766] Range#bsearch


Issue #4766 has been updated by Thomas Sawyer.


@eric So you are saying #bsearch _is_ #beach --that the minimum value return is just an aside to have the return value be useful? But won't the min value logic interfere with trying to do anything else with bsearch, e.g. "to_enum(:bsearch).max"?

Also, the proposed documentation starts out with "Returns the minimum value", so that indicates a different main purpose.
n
----------------------------------------
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