# C Program to Check Majority Element in a Sorted Array

• Write a program in C to check whether a number K is a majority element in a sorted array or not.
• How to check whether an element appears more than N/2 times in a sorted array of size N.

Given a sorted integer array of size N and a number K. We have to check whether K is majority element of given array or not.

If K appears more than N/2 times in input array then K is a majority element otherwise not a majority element.
For Example :
Input Array : 1 2 2 2 2 2 3 4 5
K = 2
2 is a Majority Element

Input Array : 1 2 2 3 4 4 5 7 8 8 8
K = 4
4 is not a Majority Element

Let inputArray be a sorted integer array of size N and K be the candidate for majority element.
Method 1 : By using linear search
• Find the mid Index of inputArray. Let it be midIndex.
• Using a for loop, traverse inputArray from index 0 to midIndex and search for first occurrence of K. Here no need to traverse whole array because if a majority element exists for inputArray then at-least it's one occurrence must be before midIndex.
• Let the index of first occurrence of K be i. If K is majority element then there must be atleast N/2 continuous occurrences of K in inputArray.
• If element at index (i + N/2) is equal to K then K is a majority element else not a majority element.
Time Complexity : O(n)

## C program to check whether an element is majority element or not using linear search

```#include &lt;stdio.h&gt;

/*
This function checks whether K is present more
than size/2 times in a sorted array or not
*/
void isMajorityElement(int *array, int size, int K) {
int i;

/* Find mid index of given array  */
int midIndex = (size%2)? (size/2+1) : (size/2);

/* Search for the first occurence of K in array */
for (i = 0; i &lt;= midIndex; i++) {
/* If first occurence of K is at index i and K is
present in all indexes from i to i + size/2 then
K is a majority element */
if (array[i] == K &amp;&amp; array[i + size/2] == K){
printf(&quot;%d is a Majority Element\n&quot;, K);
return;
}
}
printf(&quot;%d is Not a Majority Element\n&quot;, K);
}

int main(){
int array = {1,1,2,4,4,4,4,4,7};
/* Check if 4 is a Majority Element */
isMajorityElement(array, 9, 4);
/* Check if 1 is a Majority Element */
isMajorityElement(array, 9, 1);

return 0;
}
```
Output
```4 is a Majority Element
1 is Not a Majority Element
```

Method 2 : By using modified binary search to find index of first occurrence of K
We can optimize above algorithm by using modified binary search to find the index of first occurrence of K instead of linearly searching input array.
• This algorithm is similar to above mentioned algorithm except here we are using a modified binary search algorithm to find the index of first occurrence of K instead of linearly searching it.
• Now, finding first index of K becomes a O(Logn) time operation.
Time Complexity : O(Logn)

## C program to check majority element using binary search

```#include <stdio.h>

/* Returns the index of first occurence of K in sorted array.
If is not present then it returns -1. It uses a customized
binary search algorithm */
int getFirstIndex(int *array, int left, int right, int K) {
int mid;
if (right >= left) {
/* Get mid index */
mid = (left + right)/2;

/*
if array[mid] == K, then mid will be the index of first
occurence of K if either mid == 0, or array[mid-1] < K
*/
if ((array[mid] == K) && (mid == 0 || K > array[mid-1]))
/* first occurence found */
return mid;
else if (K > array[mid])
/* Recursively search on right sub array */
return getFirstIndex(array, (mid + 1), right, K);
else
/* Recursively search on left sub array */
return getFirstIndex(array, left, (mid - 1), K);
}
return -1;
}

void isMajorityElement(int *array, int size, int K) {
/* Get the index of first occurence of K in array  */
int i = getFirstIndex(array, 0, size-1, K);

/* K is not present in array, return */
if (i == -1)

/* check if the element is present more than n/2 times */
if (((i + size/2) < size) && (array[i + size/2] == K))
printf("%d is a Majority Element\n", K);
else
printf("%d is Not a Majority Element\n", K);
}

int main(){
int array = {1,1,2,4,4,4,4,4,7};
/* Check if 4 is a Majority Element */
isMajorityElement(array, 9, 4);
/* Check if 1 is a Majority Element */
isMajorityElement(array, 9, 1);

return 0;
}
```
Output
```4 is a Majority Element
1 is Not a Majority Element
```