[ruby-core:36661] [Ruby 1.9 - Feature #4766][Rejected] Range#bsearch

Issue #4766 has been updated by Yukihiro Matsumoto.

Status changed from Open to Rejected

I seriously considered about the issue, but I feel something wrong about this feature proposal.  Binary search requires the target to be ordered. In that sense, Arrays in general are not ordered, ranges are appeared to be ordered.  But "order" is in the eyes of beholder.  Once you supply the block, the ordered attribute of a range does not mean anything.  Besides that, as the example in the document shows, Range#bsearch is more indirect than say, Array#bsearch.

If we have to assume ordered status of the target anyway,
  min = ary.bsearch{|i| i >  4}
is much better than
  n = (0..ary.size).bsearch{|i| ary[i] > 4}
  min = ary[n]
isn't it?

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

Author: Yusuke Endoh
Status: Rejected
Priority: Normal
Assignee: Yukihiro Matsumoto
Category: 
Target version: 1.9.3


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://redmine.ruby-lang.org