On computing majority by comparisons (Q1181015)

The authors investigate the problem of finding an element in the larger part of a partition of an \(n\)-element set into two classes based on comparison, i.e. for any two elements there is a decision whether or not they belong to the same part. They give an algorithm, which finds such an element with at most \(n-B(n)\) comparisons, where \(B(n)\) is the number of 1's in the binary expansion of \(n\), and they show that this algorithm is optimal.