Delayed binary search, or playing twenty questions with a procrastinator

A. Ambainis; S. A. Bloch; D. L. Schweizer

doi:10.1007/s00453-001-0097-4

Delayed binary search, or playing twenty questions with a procrastinator

A. Ambainis^*
, S. A. Bloch
, D. L. Schweizer

^*Corresponding author for this work

University of California at Berkeley
Adelphi University
Barclays

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

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.

Original language	English
Pages (from-to)	641-650
Number of pages	10
Journal	Algorithmica
Volume	32
Issue number	4
DOIs	https://doi.org/10.1007/s00453-001-0097-4
Publication status	Published - 2002
Externally published	Yes

Keywords

Binary search
Delay
Fibonacci series
Golden ratio
Monotone search

Access to Document

10.1007/s00453-001-0097-4

Cite this

@article{9f3799bbebaa434d860f216c0fcad88e,

title = "Delayed binary search, or playing twenty questions with a procrastinator",

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",

author = "A. Ambainis and Bloch, \{S. A.\} and Schweizer, \{D. L.\}",

year = "2002",

doi = "10.1007/s00453-001-0097-4",

language = "English",

volume = "32",

pages = "641--650",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Delayed binary search, or playing twenty questions with a procrastinator

AU - Ambainis, A.

AU - Bloch, S. A.

AU - Schweizer, D. L.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - Binary search

KW - Delay

KW - Fibonacci series

KW - Golden ratio

KW - Monotone search

UR - https://www.scopus.com/pages/publications/0012645864

U2 - 10.1007/s00453-001-0097-4

DO - 10.1007/s00453-001-0097-4

M3 - Article

AN - SCOPUS:0012645864

SN - 0178-4617

VL - 32

SP - 641

EP - 650

JO - Algorithmica

JF - Algorithmica

IS - 4

ER -

Delayed binary search, or playing twenty questions with a procrastinator

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this