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

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.

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

#include <stdio.h> /* 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 <= 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 && array[i + size/2] == K){ printf("%d is a Majority Element\n", K); return; } } printf("%d is Not a Majority Element\n", K); } int main(){ int array[9] = {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.

## 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) printf("%d Not Found\n", K); /* 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[9] = {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