Whither binary search?

[John Machin]

Sion Arrowsmith wrote:
> John Machin <sjmachin at lexicon.net> wrote:
> >Fredrik Lundh wrote:
> >> well, people tend to use dictionaries when they need to look things up
> >> quickly...
> >... like those paper dictionaries with the words in alphabetical order
> >:-)
>
> ... where you'll notice that the really big ones are divided up into
> buckets (which just happen to be keyed on initial letter).

And languages whose scripts don't have letters use other bucket keys
like pronunciation  or (radical, stroke_count). In any case, the
buckets are printed in key order. The bucket index, if printed, is
itself sorted.

>
> Truth is that humans are lot better than computers at general
> insertion sort, and its lookup equivalent, whereas computers are much
> better at calculating hashes. So we each use a dictionary
> implementation that plays to our strengths.

Hashes are fine for simplistic applications.
| >>> hash('initialise') == hash('initialize')
| False
but those two are not very far apart in a sorted list.

Cheers,
John