From: "Haase, Konstantin" <Konstantin.Haase@...>
Date: 2011-06-01T20:20:05+09:00
Subject: [ruby-core:36666] Re: [Ruby 1.9 - Feature #4766] Range#bsearch

It might make sense for SortedSet (part if the stdlib), though.

Konstantin

On Jun 1, 2011, at 13:07 , Yusuke Endoh wrote:

> 
> Issue #4766 has been updated by Yusuke Endoh.
> 
> Target version changed from 1.9.3 to 1.9.x
> 
> Thank you for your time.
> 
> 
>> Once you supply the block, the ordered attribute of a range does not mean anything.
> 
> I'm not sure if I could understand this correctly.  If the block handles
> its parameter in terms of the ordered attribute, is there no problem?
> 
> Else, any method must work even if a supplied block ignores the context?
> Array#sort violates the rule, I think.
> 
> 
>> Besides that, as the example in the document shows, Range#bsearch is more indirect than say, Array#bsearch.
> 
> Yes, for typical cases.  But Array#bsearch is not enough since it cannot
> be used over Float or big range.
> 
> Anyway, I'm NOT against Array#bsearch.  It is a good thing.  But You
> rejected it.  Now do you accept Array#bsearch?
> 
> 
> Binary search is a practical matter than philosophy.
> Hope my proposal to get reconsidered.
> 
> -- 
> Yusuke Endoh <mame@tsg.ne.jp>
> ----------------------------------------
> 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.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
>