We consider the problem of identifying an unknown value x in { 1, 2, ... , n } by asking "Yes-No'' questions about x. The goal is to minimise the number of questions required in the worst case, taking into account that no more than B questions may receive answer "Yes'' and no more than E answers may be erroneous. We consider two version of this problem: the discrete and the continuous version. In the discrete case x is a member of the finite set { 1, 2, ..., n }; in the continuous case x is a member of the half-open real interval (0,1]. In the continuous case we will not in general be able to identify x exactly with a finite number of questions; rather we fix a size epsilon and then we compute the exact value of the minimal number of questions to get a subset of (0,1] of size epsilon which is known to contain x. The solution of the continuous version allows us to derive a lower bound for the minimal number of questions required for the discrete version of the problem.

Binary search with errors and variable cost queries

SERENO, Matteo
1998-01-01

Abstract

We consider the problem of identifying an unknown value x in { 1, 2, ... , n } by asking "Yes-No'' questions about x. The goal is to minimise the number of questions required in the worst case, taking into account that no more than B questions may receive answer "Yes'' and no more than E answers may be erroneous. We consider two version of this problem: the discrete and the continuous version. In the discrete case x is a member of the finite set { 1, 2, ..., n }; in the continuous case x is a member of the half-open real interval (0,1]. In the continuous case we will not in general be able to identify x exactly with a finite number of questions; rather we fix a size epsilon and then we compute the exact value of the minimal number of questions to get a subset of (0,1] of size epsilon which is known to contain x. The solution of the continuous version allows us to derive a lower bound for the minimal number of questions required for the discrete version of the problem.
1998
Volume 68 , Issue 5 (December 1998)
261
270
Binary search; Errors; Variable cost queries; BS-strategy
M. SERENO
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/10031
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 7
social impact