From: Michael Edgar <adgar@...>
Date: 2011-07-18T09:12:51+09:00
Subject: [ruby-core:38149] Re: [Ruby 1.9 - Feature #4766] Range#bsearch

On Jul 17, 2011, at 7:54 PM, Eric Hodel wrote:

> When performing a binary search you may have multiple matching values, the three 100 values from the example.  For the proposed implementation the first one is chosen for consistency.
> 
> Nobody knows what the #beach method you keep talking about would be.  Maybe you mean binary-search-each?  That doesn't make any sense as binary search will not yield each item in the enumerator.

I wouldn't say "nobody". I think what he's suggesting is a more flexible binary-search-each which yields all elements for which the block is true. Hear this out:

The current implementation's result is equivalent to Enumerable#min, except it requires sorted order so it can use binary search. This adds the asymptotic speedup to the #min method.

This is handy, but what if someone wanted the maximum? Or just the first element that matches?

Those are equivalent, respectively, to Enumerable#max and Enumerable#find. Personally, I think I'd usually just want to get the first one that matches, and not use extra cycles computing the minimum. There's room for choice which the current implementation lacks. Further, they can't be built based on the new method. They have to be written from scratch.

These could be implemented with a base, binary_matches method, with selection logic added on. Assume binary_matches takes a block, and returns an enumerator for all elements for which the block yields true. It can do so in O(log(n)) time. This is just a thrown together API, a better API likely exists. If you had such a method, you could implement the existing proposal (min), max, and find as such, giving all the log(n) speedup:

# The current bsearch proposal renamed to bsearch_min.
def bsearch_min(&blk)
  binary_matches(&blk).min
end

# Returns the largest elt for which the block yields true 
def bsearch_max(&blk)
  binary_matches(&blk).max
end

# Returns the first-discovered elt for which the block yields true
def bsearch_find(&blk)
  binary_matches(&blk).each do |elt|
    return elt if blk.call(elt)
  end
end

This seems useful to me.

Michael Edgar
adgar@carboni.ca
http://carboni.ca/