At 13:52 +0200 on 10/24/2013, Rob van der Heij wrote about Re: Linear
search vs binary:
On 24 October 2013 12:50, Don Higgins <d...@higgins.net> wrote:
I see discussion about optimizing the binary search, but I don't see any
discussion about optimizing linear search which might make it much faster
than binary depending on the search history. Putting the last key found at
front of most recently used list or just holding last found as a first test
may result in significant reduction in total search compares if there are
frequent repeat requests.
Sure, we made no assumption about the distribution of keys and searches and
assumed both random. In some cases you can generalize relevant information
about the distribution (like sorting an array that is already pretty good
sorted). But often it is more convenient to separate the two cases and
treat them separate using a bimodal distribution.
Using his Last Found trick, you can start at "Last Found" (bypassing
all the prior entries) if "Looking For" is greater than "Last Found".
