Find popular element in an array

Given a sorted array of integers, find a “popular” element i.e. one which occurs more than n/4 times.

If no such element exist (which occurs more than n/4 times) then print error.

For example: If Input array has 8 elements as below
    {1, 3, 3, 3, 4, 6, 9, 10}
Then 3 is the popular element that comes three times.

Solution: Brute Force - O(n)

The brute force method will traverse the array linearly and for each element 'i' it will check

if(arr[i] == arr[i+n/4])
   // arr[i] is popular elment
else
   // Continue with other element

It will take O(n) time to find the popular element using above algorithm.

Since the array is sorted, we can take advantage of some binary search type logic to reduce the time taken to lg(n).

lg(n) time algorithm

This is a two part algorithm, first we find the candidate and then we check whether any of the candidate is a popular element.

If we divide the array in 4 parts, then popular element will be first element of one of the four parts.

So, no matter how big the array is, there will always be 4 candidates for popular elements. Now, given these 4 candidates, we need to check if any one of them is popular element. To check this, for each of the 4 candidates:

1. Find first occurrence of this number in the array (it may not be at i-n/4). This takes O(lg(n)) time.
2. If first occurrence of the element is at index k, then check if the same element is also at arr[k+n/4]. This takes constant time

The time taken by this approach is sum of below three number

• Time taken to find 4 candidates - O(1)
• 4 * time taken to find first occurrence of each candidate - O(lg(n))
• 4 * Check each element whether or not it is popular - O(1)

The main logic in the solution is to find the first occurrence of a particular element in a sorted array using modified binary search.

/* Given Sorted array of size n, this function will return first occurance
 * of element 'd' in array.
 */
int bSearch(int* arr, int n, int d)
{
   int l = 0; int h = n-1;
   while(l<h)
   {
      int m = (l+h)/2;
      // First 2 cases are normal case.
      // 3rd & 4th case means that (arr[m] == d)
      // 3rd case is when we have reached the 1st occurrence of d
      // 4th case is when arr[i] is not the first occurrence,
      // In this case we will have to check the left side of m.
      if(arr[m] < d)
         l = m+1;
      else if(arr[m] > d)
         h = m-1;
      else if(m == 0 || arr[m-1] < d)
         return m;
      else
         h = m-1;
   }
   return -1;
}