Explore BrainMass

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.

    © BrainMass Inc. brainmass.com December 24, 2021, 5:42 pm ad1c9bdddf

    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.