= Solution
A strict <majority element> in the whole <array> must be a strict <majority element> in at least one half: otherwise summing the two non-<majority element> frequency bounds would give at most half of all entries. This observation supplies at most two candidates, but they must still be verified in the whole subarray.
``
majority(A, left, right):
if left == right: return NoMajority
if right - left == 1: return Candidate(A[left])
middle = floor((left + right)/2)
first = majority(A, left, middle)
second = majority(A, middle, right)
for candidate in the two returned tagged results:
if candidate is Candidate(x):
count = 0
for i from left to right-1:
if A[i] == x: count = count + 1
if 2*count > right-left: return Candidate(x)
return NoMajority
``
`NoMajority` is a separate result tag, not a possible input element. The two-candidate loop does not require ordering, hashing or conversion of arbitrary elements to a <set>. It may count the same candidate twice without changing correctness or the bound.
<Induction> proves the recursive candidates correct. If the whole subarray has a <majority element>, the observation ensures it reaches the verification step; if a candidate passes the strict frequency test, it really is a <majority element>. The worst-case recurrence has two balanced <recursive calls> and linear combination work, so the running time is \b[$\Theta(n\log n)$], with $O(\log n)$ auxiliary <recursion> depth when the <array> is passed by index ranges. A different cancellation-based method can achieve linear time, but is not needed for this divide-and-conquer construction.
Back to article page
