article · SIAM Journal on Computing · 1987
Binary Search on a Tape
Cited by 9Abstract and details only
Abstract
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.
Cite this paper
Hu, T. C., & Wachs, M. L. (1987). Binary Search on a Tape. SIAM Journal on Computing, 16(3), 573–590. https://doi.org/10.1137/0216039
Hu, T. C., and Michelle L. Wachs. “Binary Search on a Tape.” SIAM Journal on Computing, vol. 16, no. 3, 1987, pp. 573–90, https://doi.org/10.1137/0216039.
Hu, T. C., and Michelle L. Wachs. 1987. “Binary Search on a Tape.” SIAM Journal on Computing 16 (3): 573–90. https://doi.org/10.1137/0216039.
Hu, T.C. and Wachs, M.L. (1987) ‘Binary Search on a Tape’, SIAM Journal on Computing, 16(3), pp. 573–590. Available at: https://doi.org/10.1137/0216039.
@article{hu1987binary,
title = {{Binary Search on a Tape}},
author = {Hu, T. C. and Wachs, Michelle L.},
journal = {SIAM Journal on Computing},
volume = {16},
number = {3},
pages = {573--590},
year = {1987},
doi = {10.1137/0216039}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.