# Divide and Conquer majority element algorithm

The algorithm should return the majority element if it exists (majority meaning that there are $> n/2$ occurrences in the array)

I came up with this linear divide and conquer algorithm, but I'm not sure if it's correct. It returns an array with two elements, the name of the majority element and a number that is less than or equals to its occurrences. Can someone help to prove/disprove it?

def findMajority(arr):
if len(arr) == 1:
return [arr, 1]
else:
leftHalf = findMajority(arr[:len(arr)/2])
rightHalf = findMajority(arr[len(arr)/2:])

if leftHalf is None and rightHalf is not None: #Left half is indeterminate
return [rightHalf, rightHalf]

if leftHalf is not None and rightHalf is None: #Right half is indeterminate
return [leftHalf, leftHalf]

if leftHalf is None and rightHalf is None: #Both halves are indeterminate
return [None, 0]

if leftHalf == rightHalf: #Majority in both halves is the same
return [leftHalf, leftHalf + rightHalf]

elif leftHalf < rightHalf: #Right majority has more occurrences
return [rightHalf, rightHalf]

elif leftHalf > rightHalf: #Left majority has more occurrences
return [leftHalf, leftHalf]

else: #There is no winner between the two halves and they have equal occurrences
return [None, 0]


EDIT: It returns the wrong answer for [2,2,2,2,1,1,1,0,1,1,1,0,1,1,1,0] . So it doesn't work.

• @xavierm02 But in this case there is no majority, there needs to be more than $n/2$ occurrences – Jack Black Mar 3 '17 at 17:40
• @xavierm02 There is still no majority, there needs to be an element with 5 or more occurrences – Jack Black Mar 3 '17 at 17:44
• How about $[0;1;1;1]$? – xavierm02 Mar 3 '17 at 17:46
• @xavierm02 It works in this case. – Jack Black Mar 3 '17 at 17:48
• If you're looking for a linear time algorithm, try this en.wikipedia.org/wiki/… – skankhunt42 Mar 3 '17 at 17:59

It's not correct. On input [a a b c], the left side yields [a, 2], the right side yields [nil, 1]. They would be merged into [a, 2].
I'll outline a linear time solution. If there exists a value $x$ such that more than $n/2$ of the elements of $A$ have value $x$, then certainly the $n/2$-th order statistic of $A$ must be $x$. The selection problem is solved in linear time using, for example, median of medians; checking that such value does indeed appear at least $n/2$ times is trivially linear time.