Majority problem in linear time
I have been asked to create a linear time solution to the majority/majority vote problem stated as follows:
in a set of n elements if there are more than n/2 identical elements, they constitute a majority. Eg in xyxx the majority is x. I understand the Boyer-Moore solution but not its proof.
I am looking to solve the problem by perhaps finding a fast way of determining if an element is -not- part of the majority and elliminating those. My question is how I should formulate the base case for this algorithm on which to build an inductive solution. The way I see it there are at least 3 possible combinations in the smallest case: