Finding Majority

majority.py

from pprint import pprint

def find_majority(lst):
    maj = majority(lst)
    pprint(maj)
    if len(maj) > 1:
        return 'Not Found'
    else:
        return list(maj.keys())[0]

def merge(left, right, length):
    # Merge
    for k, v in right.items():
        left[k] = left.get(k, 0) + v
    # Discard
    return { k: v for k, v in left.items() if v >= length // 2 }

def majority(lst):
    if len(lst) == 1:
        return {lst[0]: 1}

    length = len(lst)
    mid = length // 2
    left = majority(lst[0:mid])
    right = majority(lst[mid:])

    return merge(left, right, length)

print(find_majority([
    1, 2,
    1, 2,
    1, 2,
    1, 3,
    2,
]))