majority_element.py

def count(a,x, left, right):
    count = 0
    for i in range(left, right+1):
        if a[i] == x:
            count+=1
    return count
def maj(a,left, right):
    if left == right:
        return a[left]
    middle = (left+right)//2
    maj1 = maj(a,left, middle)
    maj2 = maj(a,middle+1, right)
    if count(a,maj1, left, middle) + count(a,maj1,middle+1,right) > (right - left + 1)//2 :
        return maj1
    elif count(a,maj2, left, middle) + count(a,maj2,middle+1,right) > (right - left + 1)//2 :
        return maj2
    else:
        return -1