On Saturday, 17 May 2014 at 22:05:03 UTC, bearophile wrote:
monarch_dodra:
for a sorted linked list (or forward iterators in general),
you can find the result with O(N) *walk* iterations, but still
only O(log(N)) *comparison* iterations.
I think I have never implement such algorithm, but you are
right, and it's nice. Is Phobos using this idea somewhere? Are
D AAs using it?
Bye,
bearophile
It's not used in phobos (as far as I know of anyways). It *could*
be implemented in SortedRange's BinaryFind though.
As for using it in AA's, you'd have to keep in mind you'd that (I
think) you probably need a minimum size for the algorithm's lower
complexity to kick in and actually give you better times.
