Feb. 21, 2014, 4:22 p.m. by Rosalind Team

**Topics**:
Sorting

An array *majority element* if more than half of its entries are the
same.

Given: A positive integer

Return: For each array, output an element of this array occurring strictly more than

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

4 8 5 5 5 5 5 5 5 5 8 7 7 7 1 7 3 7 7 1 6 5 10 100 1000 1 5 1 6 7 1 1 10 1

5 7 -1 -1

## Discussion

It is not difficult to develop a divide-and-conquer algorithm checking whether a given array of size

$n$ contains a majority element in$O(n \log n)$ time. It is interesting to note that there is also a linear time algorithm and it is also based on divide-and-conquer.