From: "usa (Usaku NAKAMURA)" Date: 2012-11-15T16:52:17+09:00 Subject: [ruby-core:49365] [ruby-trunk - Feature #4766][Assigned] Range#bsearch Issue #4766 has been updated by usa (Usaku NAKAMURA). Status changed from Closed to Assigned in range.c, the definition of a macro BSEARCH_CHECK includes: switch (rb_cmpint(rb_funcall(v, id_cmp, 1, INT2FIX(0)), v, INT2FIX(0)) < 0) { \ case 0: return val; \ case 1: smaller = 1; \ case -1: smaller = 0; \ } \ But, in C, the value of compare expression is only 0 or 1, so this code is nonsence. What do you want to do here? ---------------------------------------- Feature #4766: Range#bsearch https://bugs.ruby-lang.org/issues/4766#change-32922 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 -- http://bugs.ruby-lang.org/