 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.