Given a sorted array [A...n] of reals, give an algorithm to determine whether A has a majority element or not.

Question

A majority element is an element that appears more that n/2 times.

My initial throught was to:
My inittial Running time would be O(n^n), because it needs to touch each element once for each element. Is there a better algorithm for my problem?

Step 1: Start with the first element. (Take every unique element) in the sorted array and count how many times each occurs.
Step 2: Store a count. If the count of another unique element is greater that count. Store that element and its count.
Step3: After traversing the entire list, compare count to n/2. If count is larger that n/2, there exists a majority element.

Example:

1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 7, 7, 9, 10

**Stored Element = Stored count**

1 = 1
2 = 1
3 = 1
4 = 1
5 = 9
6 = 1
7 = 2
9 = 1
10 = 1

After traversing, 5 = 9. Is count > n/2?

9 > 16/2, Yes. Therefore there is a majority element.

Answer 1

A majority element is an element that occurs at least n/2 times. Therefore, if there's a majority element, it must occur at position n/2. So, what I would do is:

1. Find the element x at n/2
2. Find the position p of the first occurence of x by traversing backwards
3. Check if the element at p + n/2 + 1 is equal to x

in PHP I would do something like

function hasMajorityElement($a) {
$n = count($a);
$p = $n div 2;
$x = $a[$p];
while (($a[$p-1] == $x) && ($p > 0))
$p--;
return ($a[$p+($n div 2)+1] == $x);
}

I think the complexity for this algorithm is less than O(n/2) but I'm no expert on complexity formulas.

For efficiency, if you use large sets, you should implement step 2 as a binary search.

Answer 2

I have a feeling I may be helping you do your homework, which isn't going to help you much later on. But anyway...

If there is a majority element, it will always appear in the middle of the sorted set, because there will be at least n/2+1 elements with that value. Even if the majority element has the largest or smallest value in the set, it will still reach to the middle when the values are listed in order.

So, just pick element number floor((n+1)/2). Then step up and down from there, counting how many elements have the same value as that one. If the answer is > n/2, then this is a majority element. Otherwise, there is no majority element.

Answer 3

I'm not sure exactly what an alan algorithm is. Personally I have never heard of it (but I don't doubt this exists.) I also agree with the last poster. Sort your input set S. Then iterate through each member: 1. determine what number would need to be added to that member to equal x. 2. binary search S to verify whether or not the element exists in S. The question is stated in a way to indicate that you are intersted only in the existence of a pair, rather than being interested in all pairs that sum to x. Therefore you need not continue searching once one satisfying pair has been found. Also, pay attention to things you can logically throw out. After sorting S, you can start checking for things such as members of S which are negative or are greater than x. If no negative members of S exist then you need not worry about members that are greater than x. Finally, use STL. I would create a vector of numbers: vector S; then sort using the STL sort. This will cut down on runtime and coding time. hope this helps. //////// In response to morgan's answer (below mine). Your algorithm fails if the input set S is not yet sorted. This is why I said to sort the input set first. Likewise, you could compare each element to each element, but this give you o(n^2) which is a problem if you care about that sort of thing. Also, we are not sure what an alan algorithm is. It is true that the check for a proper sum pair can be performed within your sort algorithm. This will work with certain sorting algorithms such as insertion sort. Would not advise trying to do that using merge sort or quick sort. ///////// Further edit: I think the question was changed after my initial answer, because it didn't initially say that the set was assumed to be sorted. If the set is already sorted, then the asnwer is trivial - you can follow Morgan's answer below

Answer 4

Because you are looking for the majority element you do not need to store a count of each different element value. There can only be one majority element!
So all you need to do is start counting the number of times an element value occurs.
The list is already sorted! So when the element value changes you now check the count value if it is greater than n/2 then you have your majority element. You can now exit your loop. If it is not then reset your count and start accumulating again.

Answer 5

The guy before has the right algorithm, but the efficiency is more on the order of log n if using binary search (even better!). Yay for having a sorted list!