[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.
>=20
> 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=20
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
[e-mail]
http://carboni.ca/=