Hu, T. C.; Wachs, Michelle L. Binary search on a tape. (English) Zbl 0654.68075 SIAM J. Comput. 16, 573-590 (1987). Summary: Given n records stored alphabetically on a tape, any comparison search procedure can be characterized by a binary tree. The complete binary tree (binary search) uses the minimum number of comparisons but not the minimum number of movements. The linear binary tree (sequential search) uses the minimum number of movements but not the minimum number of comparisons. A tape-optimal tree is a tree which minimizes the total cost of comparisons and movements. The tape-optimal tree is a “hybrid” of the linear tree and the complete binary tree, and is characterized for arbitrary n. Cited in 5 Documents MSC: 68P10 Searching and sorting 68P05 Data structures 05C05 Trees 68Q25 Analysis of algorithms and problem complexity 68P20 Information storage and retrieval of data Keywords:optimal file search procedure; sequential access file; binary tree; binary search; sequential search PDFBibTeX XMLCite \textit{T. C. Hu} and \textit{M. L. Wachs}, SIAM J. Comput. 16, 573--590 (1987; Zbl 0654.68075) Full Text: DOI