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.
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.
Boyer–Moore majority vote algorithm Python code:
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