the minimum no of comparisons required to find Majority Element in a sorted array (note that key is not given).

Question

for example array contain a[1 2 3 3 3 3 3 4 5] then retun(1)

Answer 1

if any element is present more than n/2 times in the array then that element is called majority element.The best way to implement this is through a BST.Node of the Binary Search Tree: struct tree { int element; int count; }BST; Insert elements in BST one by one and if an element is already present then increment the count of the node. At any stage, if count of a node becomes more than n/2 then return. ref:http://www.geeksforgeeks.org/majority-element/

Comments

can't be this done in one comparison?

since array is sorted and the majority element must be present at the middle position

---

Array is already sorted, so to count element that appears max number of times in this array, O(n) time is required.

Take two variables max and count and initialize them as 0 and 1 resp

For i=2 to n

If a(i) is not same as a(i-1),  Check whether count > max, then assign count to max and reset count as 1.

else count ++

At the end of the loop max contains maximum no of times any element has repeated.

If the majority element is also required maintain a variable key and update it accordingly with max.

if max is 1 then majority element does not exists.

---

findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a) If a[maj_index] == a[i]
          count++
    (b) Else
        count--;
    (c) If count == 0
          maj_index = i;
          count = 1
3.  Return a[maj_index]

after finding candidate element by Using Moore’s Voting Algorithm

then check that candidate appears more than n/2 times then called to be majority element