Explore BrainMass

# Algorithm to find majority element

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Let A be an array of n elements. An element x is said to be a majority element in A if it occurs in A more than n/2 times. Assume that the only comparisons allowed between elements are tests of equality. Give an algorithm that uses no more than 2n comparisons to determine whether the array A contains a majority element and, if so, find it.

https://brainmass.com/computer-science/arrays/algorithm-to-find-majority-element-63442

#### Solution Preview

Soln 1.

If there is a majority element, it must be the median. So use the average-time RANDOMIZED-SELECT algorithm (RANDOMIZED-SELECT finds any ith order statistic in linear time, and the median is simply the "middle" order statistic) to find a candidate majority ...

#### Solution Summary

An Algorithm to find majority element is featured.

\$2.49