HNGlance

Top Best New Show

Hop lists

http://www.dekorte.com/blog/blog.cgi?do=item&id=3804

by epe • 18 years ago

4 1 18 years ago

DE

Related Stories

Loading related stories...

Comments

1

ganley• 18 years ago

At a glance, I'm pretty sure this doesn't work. The average jump is not to the bisection between the current node and the node you're seeking, it's to the bisection between the current node and the end of the list. As you get closer to the node you seek, the probability gets higher and higher that the skip link points past the node you seek, in which case it does nothing for you and you continue sequentially searching. I haven't done the math, but I think the expected search is O(n) - though possibly faster in practice than a simple sequential search.

Source preview

dekorte.com

HNGlance

© 2024-2026 HN Glance. Story content belongs to its original sources.

Privacy
Terms