Boyer-Moore voting use case.
In Computer science the Boyer-Moore voting algorithm is a famous optimal algorithms which is used for finding the majority element among the given elements list that have more than N/ 2 occurrences. This algorithm uses the logic that if an element occurs more than N/2 times, the remaining elements other than this would certainly be less than half of the list. The name of the algorithm comes after it's inventors Robert S. Boyer and J Strother Moore, who published it in 1981.
Python Knowledge Base: Make coding great again.
- Updated:
2024-07-26 by Andrey BRATUS, Senior Data Analyst.
Boyer–Moore majority vote algorithm Python code:
Boyer–Moore algorithm Python code result:
The process logic is simple:
- Сhoose a candidate from the given set of elements.
- Iterate from input elements, if the element is equal to candidate element, increase the votes.
- Otherwise, decrease the votes.
- If votes become 0, choose a new candidate.
def findMajority(arr, n):
candidate = -1
votes = 0
# Finding majority candidate
for i in range (n):
if (votes == 0):
candidate = arr[i]
votes = 1
else:
if (arr[i] == candidate):
votes += 1
else:
votes -= 1
count = 0
# Checking if majority candidate occurs more than n/2 times
for i in range (n):
if (arr[i] == candidate):
count += 1
if (count > n // 2):
return candidate
else:
return -1
# Driver Code
arr = [ 2, 2, 2, 4, 2, 11, 3, 5, 2, 7, 2 ]
n = len(arr)
majority = findMajority(arr, n)
print(" The majority element is :" ,majority)
OUT: The majority element is : 2