Noisy (Binary) Searching: Simple, Fast and Correct

Dariusz Dereniowski, Aleksander Łukasiewicz, Przemysław Uznański

This work considers the problem of the noisy binary search in a sorted array. The noise is modeled by a parameter $p$ that dictates that a comparison can be incorrect with probabil…