Hacking the $O(n)$ Find
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 linked list, if the target item is likely to be searched for again soon.
Exercise Can we apply the move-to-front heuristic to speed up linear search in an array?
Solution
Maybe! Moving the target of a search 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 "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 move-to-front heuristic for an array and keep it a constant time operation (at the cost of more complex implementations such as 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.