Checking whether at least n/2 + 1 elements of a set/vector are equal We have a set of elements, say a vector of $n$ elements (actually, the data structure really doesn't matter in this case). It is NOT sorted. We want to check whether at least $n/2 + 1$ elements are equal. 

I have been thinking about an efficient algorithm to do so but I don't know, the fact that it is not sorted makes it quite difficult for me.

If it was sorted, we could do it with an $O(n)$ algorithm, I'd say: just iterate over the vector, saving the most common element. If the counter arrives to $n/2 + 1$, we are done.

Could you give me some advice? Thank you very much.
I think there is an even better approach to your problem: 


The element you are looking for will also be the median of the list. Find the median of the list using the Median of Medians algorithm. $O(n)$ complexity
Check if the median appears at least $n/2 + 1$ times on the list $O(n)$ complexity


So, the algorithm you're looking for runs in linear time.