From: Yusuke Endoh Date: 2011-07-20T11:21:11+09:00 Subject: [ruby-core:38234] [Ruby 1.9 - Feature #4766] Range#bsearch Issue #4766 has been updated by Yusuke Endoh. File bsearch.patch added Hello, Let me summarize. There are two typical use cases for bsearch: from array soreted in ascending order, 1) find minimum i so that s <= a[i] 2) find any i so that s == a[i] Case 2 is the point I overlooked; "find minimum" is not inherent in binary search. In fact, the API that I proposed covers both use cases. 1) r.bsearch {|i| s <= a[i] } 2) r.bsearch {|i| break i if s == a[i]; s < a[i] } But, > My proposed bsearch_matches would clearly need to know which > direction to break ties before it commenced (perhaps a 1/0/-1 > argument), which starts to limit its usefulness. indeed, Case 2 can be shorter by using 1/0/-1. 2) r.bsearch {|i| s - a[i] } As Michael said, it is too cryptic for casual use, but certainly more generic, and compatible to bsearch of stdlib.h. How about combining 1/0/-1 and my proposal? That is, if the block returns zero, the current value satisfies the condition; return the current value immediately if the block returns an integer less than zero, the current value is too big to satisfy the condition; continue to search smaller values if the block returns an integer greater than zero, the current value too big to satisfy the condition; continue to search larger values if the block returns true, the current value satisfies the condition; continue to search minimum bound if the block returns false or nil, same as -1 It is still needed to invert the condition when you want the maximum bound, but I guess this is acceptable compromise. I updated rdoc and a patch. As you know I'm not a native speaker, so could you check it? /* * call-seq: * rng.bsearch {|obj| block } -> element * * By using binary search, finds a value in range which meets the given * condition in O(n log n) where n = (rng.begin - rng.end). * * The given block receives a current value, determines if it meets the * condition and controls search. * When the condition is satisfied and you want to stop search, the block * should return zero, and then this method return the value immediately. * When the condition is satisfied and you want to find minimum bound, * the block should return true. When the condition is not satisfied and * the current value is smaller than wanted, the block should return false, * nil or an integer greater than zero. When the condition is not satisfied * and the current value is larger than wanted, the block should return an * integer less than zero. * Unless the block returns zero, the search will continue until a minimum * bound is found or no match is found. Returns the minimum bound if any, * or returns nil when no match is found. * * The block must be monotone; there must be two values a and b so that * the block returns: * - false, nil or an integer greater than zero for all x of [begin of * range, a), and * - zero or true for all x of [a, b), and * - an integer less than zero for all x of [b, end of range). * If the block is not monotone, the result is unspecified. * * This method takes O(n log n), but it is unspecified which value is * actually picked up at each iteration. * * 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 * * ary = [0, 100, 100, 100, 200] * (0..4).bsearch {|i| 100 - i } #=> 1, 2 or 3 * (0..4).bsearch {|i| 300 - i } #=> nil * (0..4).bsearch {|i| 50 - i } #=> nil */ Thanks, -- Yusuke Endoh ---------------------------------------- Feature #4766: Range#bsearch http://redmine.ruby-lang.org/issues/4766 Author: Yusuke Endoh Status: Assigned Priority: Normal Assignee: Yusuke Endoh 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 -- http://redmine.ruby-lang.org