And here's another interesting algorithm/structure: Randomized Slide to Front

[CraigDillabaugh via Digitalmars-d]

On Monday, 30 November 2015 at 21:33:31 UTC, Andrei Alexandrescu 
wrote:
> Now that we got talking about searching in arrays, allow me to 
> also share an idea I've had a short while ago.
>
> [...]

Perhaps some strategy similar to Working Sets: 
https://en.wikipedia.org/wiki/Iacono's_working_set_structure 
would work (or inspired by the same idea).  You move the element 
from where it is found to T_1, move a random element from T_1 to 
T_2, from T_2 to T_3 and so on to T_i. In this case rather than 
trees you would have lists.  Maybe that has poor cache locality 
properties though.