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 <mame / tsg.ne.jp> > ---------------------------------------- > 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 <mame / tsg.ne.jp> >=20 >=20 > --=20 > http://redmine.ruby-lang.org >=20