Majority Element using divide-and-conquer algorithm

Question

everyone! An element of a sequence of length n is called a majority element if it appears in the sequence strictly more than n/2 times.

The goal in this code problem is to check whether an input sequence contains a majority element.

I'm trying to solve this problem, using merge sorting algorithm

My strategy:

1. Sort sequence, using merge algorithm

2. Find an occurrence of each element in sorted list. If it is more than n/2, return 1. As the list is sorted I want to go through the list, and if next element is differs from previous one counter stops and compare it with n/2

   def merge(left,rigt):
       result = []
       i = j = 0
       while i < len(left) and j < len(rigt):
           if left[i] <= rigt[j]:
               result.append(left[i])
               i += 1
   
           else:
               result.append(rigt[j])
               j += 1
   
       result += left[i:]
       result += rigt[j:]
   
       return result
   
   def merge_sort(a):
   if len(a) <= 1:
       return a
   
   middle = len(a)//2
   
   left = a[:middle]
   right = a[middle:]
   
   left = merge_sort(left)
   right = merge_sort(right)
   
   return list(merge(left,right))
   
   def get_major_element(a,n):
   
   k = 1
   
   for i in range(0,len(a)-1):
       if a[i] == a[i+1]:
           k += 1
   
   if k > n/2:
       return 1
   
   else:
       return 0
   
   if __name__ == '__main__':
       input = sys.stdin.read()
       data = list(map(int, input.split()))
       n = data[0]
       a = data[1:]
       m = merge_sort(a)
       print (get_major_element(m,n))
   

The result I get is invalid. I guess, that I can do that without initial sorting, but I can't get which step should I rewrite! Can anyone help please?

Answer 1

Divide your array into two halves, the left half and the right half. Note that if an element is the majority of the whole array, then it's the majority of at least one of the halves.

So to find the majority of an array, recursively find the majority of both halves, and then with a single pass on the array count how many times both of the candidates appear in the whole array, to check which of them is the majority of the whole array.