= Divide-and-conquer majority element
An entry occurring strictly more than half the time in an <array> must occur strictly more than half the time in at least one half: otherwise the two frequency bounds sum to at most half the whole length. Recursively find each half's possible <majority element>, then verify at most two candidates over the whole subarray using only equality tests. <Induction> proves correctness, and linear combination work over a balanced <recursion> tree gives worst-case $\Theta(n\log n)$ time. A tagged absent result avoids confusing failure with a valid element.
Back to article page
