[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:

>=20
> Issue #4766 has been updated by Yusuke Endoh.
>=20
> Target version changed from 1.9.3 to 1.9.x
>=20
> Thank you for your time.
>=20
>=20
>> Once you supply the block, the ordered attribute of a range does not mea=
n anything.
>=20
> 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?
>=20
> Else, any method must work even if a supplied block ignores the context?
> Array#sort violates the rule, I think.
>=20
>=20
>> Besides that, as the example in the document shows, Range#bsearch is mor=
e indirect than say, Array#bsearch.
>=20
> Yes, for typical cases.  But Array#bsearch is not enough since it cannot
> be used over Float or big range.
>=20
> Anyway, I'm NOT against Array#bsearch.  It is a good thing.  But You
> rejected it.  Now do you accept Array#bsearch?
>=20
>=20
> Binary search is a practical matter than philosophy.
> Hope my proposal to get reconsidered.
>=20
> --=20
> Yusuke Endoh <[e-mail]>
> ----------------------------------------
> Feature #4766: Range#bsearch
> http://redmine.ruby-lang.org/issues/4766
>=20
> Author: Yusuke Endoh
> Status: Rejected
> Priority: Normal
> Assignee: Yukihiro Matsumoto
> Category:=20
> Target version: 1.9.x
>=20
>=20
> Hello,
>=20
> I propose Range#bsearch for binary search:
>=20
>  ary =3D [0, 4, 7, 10, 12]
>  p (0..4).bserach {|i| ary[i] >=3D 4 } #=3D> 1
>  p (0..4).bserach {|i| ary[i] >=3D 6 } #=3D> 2
>=20
>  p (0.0...Float::INFINITY).bsearch {|x| Math.log(x) >=3D 0 } #=3D> 1.0
>=20
>=20
> Rdoc:
>=20
> *  call-seq:
> *     rng.bsearch {|obj| block }  -> element
> *
> *  Returns the minimum value in range which meets the block by binary sea=
rch.
> *  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 v=
alue
> *      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 =3D [0, 4, 7, 10, 12]
> *     (0...ary.size).bsearch {|i| ary[i] >=3D 4 } #=3D> 1
> *     (0...ary.size).bsearch {|i| ary[i] >=3D 6 } #=3D> 2
> *     (0...ary.size).bsearch {|i| ary[i] >=3D 8 } #=3D> 3
> *     (0...ary.size).bsearch {|i| ary[i] >=3D 100 } #=3D> nil
> *
> *     (0.0...Float::INFINITY).bsearch {|x| Math.log(x) >=3D 0 } #=3D> 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 =3D [0, 100, 100, 100, 200]
> *     (0..4).bsearch {|i| p ary[i]; ary[i] >=3D 100 }
> *       # may output "100" more than once
>=20
>=20
>=20
> Discussion:
>=20
> You might think Array#bsearch is better.  But Array#bsearch has some prob=
lems:
>=20
>  - 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:
>=20
>      ary.sort!
>      i =3D (0...ary.size).bsearch {|i| condition(ary[i]) }
>      p ary[i]
>=20
>  - matz hated Array#bsearch because its precondition (Array must be sorte=
d)
>    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.
>=20
>=20
> I think there is demand for this feature because similar feature requests
> are often proposed: [ruby-dev:17122] [ruby-core:30892] [ruby-dev:38545]
>=20
> More importantly, this feature is often required in many programming
> contests :-)
>=20
>=20
> A patch is attached.  Thank you for your consideration.
>=20
> --=20
> Yusuke Endoh <[e-mail]>
>=20
>=20
> --=20
> http://redmine.ruby-lang.org
>=20