Re: Binary Search

In message <imikdg120s@xxxxxxxxxxxxxxxxx>, Michael Wojcik wrote:

Patricia Shanahan wrote:

I would recommend comparing its performance to a linear search with the
data in descending order of historical access frequency.

You could implement the latter constraint (data in descending order of
access) dynamically using a move-to-front list, though you'd want a
data structure that offers cheap insertion at the front.

Or you could simply maintain an access counter attached to each element, and
re-sort after every, say, 10**n lookups (for n ≥ 3 or something).
.