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

How about unsorted array?

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

**supriyas**#1

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

@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.

**supriyas**#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

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.