More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case

DOI10.1137/0220010MaRDI QIDQ3204043zbMATH OpenOpenAlexFDO

Authors Edward M. Reingold, Xiaojun Shen

Publication date 1991

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0220010

zbMATH Keywords

optimal algorithmsprefix-freeunbounded searchAckermann's functionKraft's inequality

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Prefix, length-variable, comma-free codes (94A45) Parallel algorithms in computer science (68W10) Rate of growth of functions, orders of infinity, slowly varying functions (26A12)

Recommendations

• More Nearly Optimal Algorithms for Unbounded Searching, II:The Transfinite Case
• Unbounded Searching Algorithms
• A generalization of binary search
• Universal coding of integers and unbounded search trees
• Search in an Ordered Array Having Variable Probe Cost

Cited in

(8)

• A generalization of binary search
• scientific article; zbMATH DE number 861625 (Why is no real title available?)
• On the unsolvability of problems of guaranteed search in a sufficiently large domain
• More Nearly Optimal Algorithms for Unbounded Searching, II:The Transfinite Case
• scientific article; zbMATH DE number 63650 (Why is no real title available?)
• Unbounded Searching Algorithms
• scientific article; zbMATH DE number 3943024 (Why is no real title available?)
• How many probes are needed to compute the maximum of a random walk?

This page was built for publication: More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3204043)