[ruby-core:48354] [ruby-trunk - Feature #4766] Range#bsearch

Issue #4766 has been updated by ko1 (Koichi Sasada).


ping. status?

----------------------------------------
Feature #4766: Range#bsearch
https://bugs.ruby-lang.org/issues/4766#change-31663

Author: mame (Yusuke Endoh)
Status: Assigned
Priority: Normal
Assignee: mame (Yusuke Endoh)
Category: 
Target version: 2.0.0


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 <[e-mail]>


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