Searching on a Tape

This paper considers the problem of minimizing the average time to search for a key in a stored list of keys in a sequential access machine model (SAM), e.g., a magnetic tape, where both the time to access a key in the list and the time to compare it to the given search key are taken into account. The time to access a key in the list is assumed proportional to the distance the head moves from its current location to reach the key. The time to read and compare the key to the search key is taken to be constant. Two classes of algorithms are analyzed and a matching lower bound on the average search time is presented. These results answer an open problem posed by Nishihara and Nishino [11] regarding the optimal search algorithm for such a model. Finally, it is shown that the organization of the input data is crucial in determining the SAM complexity of the search problem.