Localized search in sorted lists
S. Rao Kosaraju · 1981
It is well known that every one of the set operations insert, delete and member can be performed in O(log n) steps, where n is the number of elements currently in the set. Here we implement these operations and a move operation for a sorted list with f fingers (points of reference) established on the list. It is shown that these operations can be performed in O(log d) steps, where d is the distance between the corresponding finger and the key involved.