4 ms·

A similar idea is finger search (https://en.wikipedia.org/wiki/Finger_search https://en.wikipedia.org/wiki/Finger_search), where you can turn a traversal of a t

A similar idea is finger search (https://en.wikipedia.org/wiki/Finger_search https://en.wikipedia.org/wiki/Finger_search), where you can turn a traversal of a tree from O(log(number of items in the tree)) into O(log(number of items between the finger and the key)).

uyt 5y ago
I was going to link the same thing except I would say he is talking about exactly that without knowing the academic name for it.
namibj 5y ago
A related thing: exponential search. It's the sorted-array equivalent.