Binary search on coin heads probability
This is addressed in the following paper of Karp and Kleinberg:


  Karp, Richard M.; Kleinberg, Robert. Noisy binary search and its applications. Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 881--890, ACM, New York, 2007. 


You can find a copy on Kleinberg's website.