## Abstract

The problem is considered of identifying an unknown value x belonging left brace 1,2,. . . ,n right brace using only comparisons of x to constants when as many as E of the comparisons may receive erroneous answers. For a continuous analog of this problem it is shown that there is a unique strategy that is optimal in the worst case. This strategy for the continuous problem is then shown to yield a strategy for the original discrete problem that uses log//2n plus E multiplied by (times) log//2log//2n plus O(E multiplied by (times) log//2E) comparisons in the worst case. This number is shown to be optimal even if arbitrary ″Yes-No″ questions are allowed. It is shown that a modified version of this search problem with errors is equivalent to the problem of finding the minimal root of a set of increasing functions. The modified version is then also shown to be of complexity log//2n plus E multiplied by (times) log//2log//2n plus O(E multiplied by (times) log//2E).

Original language | English (US) |
---|---|

Title of host publication | Unknown Host Publication Title |

Publisher | ACM |

Pages | 227-232 |

Number of pages | 6 |

State | Published - 1978 |

Event | Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp - San Diego, CA, USA Duration: May 1 1978 → May 3 1978 |

### Other

Other | Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp |
---|---|

City | San Diego, CA, USA |

Period | 5/1/78 → 5/3/78 |

## ASJC Scopus subject areas

- Engineering(all)