Delayed Binary Search, or Playing Twenty Questions with a Procrastinator |
| |
| Authors: | Ambainis Bloch and Schweizer |
| |
| Affiliation: | (1) Computer Science Division, University of California, Berkeley, CA 94720, USA. ambainis@cs.berkeley.edu., US;(2) Department of Mathematics and Computer Science, Adelphi University, Garden City, NY 11530, USA. sbloch@adelphi.edu., US;(3) Barclays Global Investors, 45 Fremont Street, San Francisco, CA 94105, USA. dls@aya.yale.edu., US |
| |
| Abstract: | Abstract. We study the classic binary search problem, with a delay between query and answer. For all constant delays, we give matching
upper and lower bounds on the number of queries. |
| |
| Keywords: | , Binary search, Delay, Fibonacci series, Golden Ratio, Monotone search, |
| 本文献已被 SpringerLink 等数据库收录！ |
|
