Hacking the $\Omicron(n)$ Find
- Understand the "transpose sequential search" heuristic well enough to implement it.
Recall we can use a heuristic that moves the target of a search to the head of a list, so it is found faster next time. This technique is called "move-to-front heuristic". It speeds up linear search performance in the linked list if the target item is likely to be searched again soon.
Exercise Can we apply the move-to-front heuristic to speed up linear search in an array?
Solution
Maybe! Moving the search target to the front of an array requires shifting all the other elements to the right. This is an additional linear time operation (in addition to the linear search).
Aside-1: It would not be a good idea to implement the "move-to-front" heuristic in an array by swapping the target with the front value (instead of "moving" the target element to the front). (Think why?)
Aside-2: It is possible to implement a move-to-front heuristic for an array and keep it a constant time operation (at the cost of more complex implementations such as a circular array). (Think how?)
A more common strategy is "transpose sequential search" heuristic. Look up Wikipedia's entry on Techniques for rearranging nodes in Self-organizing list for more information.