Boyer-Moore Majority Vote Algorithm

The Boyer-Moore majority vote algorithm finds the majority element of a sequence using linear time and only a constant number of words of memory, and is named after Robert Boyer and J Strother Moore, who published it in 1981 as a prototypical streaming algorithm. In its simplest form it finds an element that occurs for more than half the elements of the input, if one exists, and a second pass through the data can verify that the element found in the first pass really is a majority; without that second pass the algorithm cannot detect that no majority exists, and if none exists the element it returns can be arbitrary. It is not possible for a streaming algorithm to find the most frequent element of a sequence in less than linear space when the number of repetitions can be small.