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

DOI10.1137/0220010zbMATH Open0716.68046OpenAlexW2010091510MaRDI QIDQ3204043FDOQ3204043

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

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

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)

Cited In (8)

• A generalization of binary search
• On the unsolvability of problems of guaranteed search in a sufficiently large domain
• Title not available (Why is that?)
• More Nearly Optimal Algorithms for Unbounded Searching, II:The Transfinite Case
• Title not available (Why is that?)
• Unbounded Searching Algorithms
• Title not available (Why is that?)
• 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)