Finding an Approximate Maximum
Noga Alon, Yossi Azar · SIAM Journal on Computing · 1989
Suppose that there are n elements from a totally ordered domain. The objective is to find, in a minimum possible number of rounds, an element that belongs to the biggest ${n / 2}$, where in each round one is allowed to ask n binary comparisons. It is shown that $\log ^ * n + \Theta (1)$ rounds are both necessary and sufficient in the best algorithm for this problem.