Divide-and-conquer majority element 2026-10-24
View more
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 time. A tagged absent result avoids confusing failure with a valid element.
Read the full article
Majority element 2026-10-24
View more
An entry occurring strictly more than half the time in a finite array or sequence. At most one distinct value can satisfy this condition: two such occurrence counts would sum to more than the input length. A majority element need not be the smallest, largest or most recently observed entry.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Functional programming, design and analysis of algorithms (resit) / 5 / c / Solution 2026-10-25
View more
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 , with 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.
Read the full article