File Exchange

image thumbnail

Boyer–Moore majority vote algorithm

version 1.0.0.0 (1.45 KB) by Reza Ahmadzadeh
Boyer–Moore majority vote algorithm

4 Downloads

Updated 09 Dec 2015

View License

%% Boyer–Moore majority vote algorithm
% The Boyer-Moore Vote Algorithm solves the majority vote problem in
% linear time O(n) and logarithmic space O(\log n). The majority vote
% problem is to determine in any given sequence of choices whether
% there is a choice with more occurrences than all the others, and if so,
% to determine this choice. Mathematically, given a finite sequence
% (length n) of numbers, the object is to find the majority number
% defined as the number that appears more than floor(n/2) times.%
%
% Example:
%
% consider we want to find the majority element in 'aaaccbbcccbcc'
% MajorityVote('aaaccbbcccbcc')
% ans =
% c
%

Comments and Ratings (2)

Hi Kwame,
For an element to be considered as majority, there is a condition that says: the number of occurrence for that element has to be bigger than half of the number of elements in the sequence. In the example MajorityVote('12323234232') the element 2 has been occurred 5 times, but 5<floor(11/2) is not satisfied, so there is no majority. The answer is the same for your next example MajorityVote('3344555') where the element 5 has been repeated 3 times and floor(7/2)=3 and since 3>3 is not valid there is no majority.

Hello Reza, I tried your code using MajorityVote('12323234232') and the answer was "There is no Majority" while in fact, the answer is 2. I also tried MajorityVote('3344555') and instead of the answer being 5, it again gave me "There is no Majority". However, MajorityVote('AAAAAAAACCCCBBB') = A which is correct. Also, MajorityVote('12222') = 2 which is correct. Is the code behaving as you would expect? thanks

MATLAB Release Compatibility
Created with R2007a
Compatible with any release
Platform Compatibility
Windows macOS Linux