A simultaneous search problem

E. C. Chang, C. Yap

Research output: Contribution to journalArticlepeer-review


We introduce a new search problem motivated by computational metrology. The problem is as follows: we would like to locate two unknown numbers x, y ε [0, 1] with as little uncertainty as possible, using some given number k of probes. Each probe is specified by a real numbe r ε [0, 1]. After a probe at r, we arc told whether x ≤ r or x ≥ r, and whether y ≤ r or y ≥ r. We derive the optimal strategy and prove that the asymptotic behavior of the total uncertainty after it probes is 13/7 2-(k+1)/2 for odd k and 13/10 2-k/2 for even it.

Original languageEnglish (US)
Pages (from-to)255-262
Number of pages8
JournalAlgorithmica (New York)
Issue number2
StatePublished - 2000


  • Algorithm
  • Binary search
  • Comparison model
  • Metrology
  • Probe model

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics


Dive into the research topics of 'A simultaneous search problem'. Together they form a unique fingerprint.

Cite this