- 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.
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;
}
Output4 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;
}
Output4 is a Majority Element 1 is Not a Majority Element