Efficient algorithm to check whether a element occurs more than n/2 times in a sorted array?


#1

Efficient algorithm to check whether a element occurs more than n/2 times in a sorted array?
How about unsorted array?


#2

Anything to do with https://en.wikipedia.org/wiki/Boyer–Moore_majority_vote_algorithm


#3

For sorted array, this can be done in O(log n)

That element must be a middle element.
And to make sure that middle element occurs n/2 times, first find the first occurence of this element(using binary search) which can be done in O(log N).

Now check the N/2+ first occurence index
if it is same as the middle element, then it is occuring more than N/2 times, else no other element has that much frequency in the array


#4

The element need not be middle,consider

3 3 3 6 7 7 2 3 3 3


#5

@supriyas your array is not sorted,

considering the sorted array, your input would be 2 3 3 3 3 3 3 6 7 7. And here middle element is definitely 3.


#6

yaa u r right the middle element is the only sole candiate for the element which can repeat more than n/2 times,rest is to make sure.
Must have been sleepy while writing that example :slight_smile:

Thats a interesting algorithm,first you say I know who cant repeat more than n/2 times,there is only candidate which can repeat more than n/2 times,but Im not sure,ok so what you need to become sure?
I need log(n) comparisions to be made in the worst case.