Empower Your Python Projects with Boyer-Moore Majority Vote Algorithm.

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.

Boyer–Moore majority vote algorithm.
Boyer–Moore majority vote meme.

Python Knowledge Base: Make coding great again.
- Updated: 2024-07-23 by Andrey BRATUS, Senior Data Analyst.

    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.

  1. 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
                if (arr[i] == candidate):
                    votes += 1
                    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
            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)

  3. Boyer–Moore algorithm Python code result:

  4. OUT: The majority element is : 2

See also related topics: