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

^*Šī darba korespondējošais autors

University of California at Berkeley
Adelphi University
Barclays

Zinātniskās darbības rezultāts: Devums žurnālam › Zinātniskais raksts (žurnālā) › koleģiāli recenzēts

11 Atsauces (Scopus)

Kopsavilkums

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.

Oriģinālvaloda	Angļu
Lapas (no-līdz)	641-650
Lapu skaits	10
Žurnāls	Algorithmica
Sējums	32
Izdevuma numurs	4
DOIs	https://doi.org/10.1007/s00453-001-0097-4
Publikācijas statuss	Publicēts - 2002
Ārēji publicēts	Jā

Piekļuve Dokumentiem

10.1007/s00453-001-0097-4

Citi faili un saites

Saite uz publikāciju Scopus

Citēt šo

@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

Kopsavilkums

Piekļuve Dokumentiem

Citi faili un saites

Nospiedums

Citēt šo