Boyer–Moore Majority Vote
Replay candidate/counter cancellation, then a distinct full verification pass.
Free theory articleReplay candidate/counter cancellation, then a distinct full verification pass.
Concept & interpretation
The Boyer-Moore Majority Vote algorithm finds a majority element in a sequence if one exists. A majority element is defined as an element that occurs strictly more than n/2 times in a sequence of length n. The algorithm accomplishes this efficiently in two passes (or phases) with O(n) time and O(1) voting state. This teaching view additionally stores the entered sequence and an O(n) event trace; it does not claim constant total storage.
Experiment
Use the Boyer–Moore Majority Vote module to explore this algorithm interactively.
- Set the Sequence to
1,2,3. - Click Finish. Notice how a candidate remains at the end of the cancellation phase, but the verification phase shows it has only 1 occurrence (1 is not > 1.5). Thus, there is No majority.
- Click Reset and change the Sequence to
2,1,2,2,3,2,2. - Use Step to advance one event at a time, observing how the counter increments on matches and decrements on mismatches, before transitioning to the verification phase to count occurrences.