In this article, we will be learning how to find the majority element in a sorted array. This involve using Linear Search, Binary Search and a constant time algorithm.

Contents

1. Introduction to the Problem
   • Inputs
   • Output
   • Sample Input and Output
   • Approaches to solve the problem
2. Approach 1: Linear Search
   • Code for Approach 1
   • Output
   • Time and Space Complexity of the Approach
3. Approach 2: Using Binary Search
   • Code for Approach 2
   • Output
   • Time and Space Complexity of the Approach
4. Approach 3: O(1) time
   • Code for Approach 3
   • Output
   • Time and Space Complexity of the Approach

Introduction to the Problem

We are given a sorted array and we have to find the majority element in it.
Let's assume that the element that ocurs more than n/2 times is the majority element.So the element appears more than floor number of n/2.

Inputs

The inputs to us are :

1. Sorted array
2. The size of the array

Output

It prints the majority element if the element is present in the array.
and prints it is not present if it is not present.

Sample Input and Output

input array: 2 3 3 3 3 4
size of array:6

output : majority element is present in the given array and it is 3

input array: 6 22 22 22 34 45 56 78
size of array:8

output :Majority element is not present in the given array

input array: 8 9 9
size of array:3

output :it is majority element of the given array

Approaches to solve the problem

There are many approaches for solving the problem .Two of these approaches are same as that of the types of searches.

They are:

1. Linear Search
2. Binary Search
3. When the given condition is that the majority element is present in the array.

Approach 1:Linear Search

We will find the n/2 th element and store it in value.Then we will use linear search to find the count of the element in the array.If it is more than floor value of n/2 then it is the majority element otherwise no majority element is present.

Lets take one example and trace the steps:

Let the array be:
4 6 8 9 9 9 9

Here the size of array is 7
so n/2 is 3

The element at index 3 is 9.We store it to variable value.

Now we will do linear search for value in the array and increment count if found.

First element is 4
count is 0.

First element is 6
count is 0.

First element is 8
count is 0.

First element is 9
count is 1.

First element is 9
count is 2.

First element is 9
count is 3.

First element is 9
count is 4.

As count=4 is greater than n/2=3 the majority element is 9.

Code for Approach 1

# include <stdio.h>
# include <stdbool.h>

void main()
{
	int arr[] ={4, 6, 8, 9, 9, 9, 9};
	int n = 7;
	int count=0;
	int value;

	int i;


	int mid= n/2;
    
    value=arr[mid];

	
	for (i = 0; i < n; i++)
	{
		
		if (arr[i] == value)
			count++;
	}
	

	if (count>mid)
	{
		printf("%d appears more than %d times in array,it is majority element",value, mid);
	}
	else
	{
		printf("No majority element present");
	}
	
}

Output

9 appears more than 3 times in array,it is majority element.

...Program finished with exit code 0
Press ENTER to exit console.

Now the case when majority element is not present:

The array is 4, 6, 8, 8, 9, 9, 9

Here the size is 7
n/2=3
The element at 3 is 8.
By linear search the count of 8 is 2 which is less than 3.
Hence no majority element present.

Output

No majority element present

...Program finished with exit code 0
Press ENTER to exit console.

Time and Space Complexity of the Approach

As we are using linear search and we have a for loop of index varying from 0 to n ,the time complexity is O(n).

As no auxillary space is used the space complexity is O(1).

Approach 2 :Using Binary Search

Here instead of linear search we will use binary search to find the majority element.We will find the n/2 th element and store it in variable value.We will use binary search to find the count of the element.we will print it is the majority element if its count is greater than n/2 and if it is not then print no majority element is present.

Lets take one example and trace the steps:

Let the array be:
6 9 14 14 14 14 19

Here the size of array is 7
so n/2 is 3

The element at index 3 is 14.We store it to variable value.

Now we will do binary search for value in the array and increment count if found.

mid=n/2=3
Element at index 3 is 14
count is 1.

Now we will go to both left and right of the array

For left subarray the end index=mid-1=2
The new mid is 0+2/2=1
Element at index 1 is 9
count is 1.

For right subarray the start index=mid+1=4
The new mid is 4+6/2=5
Element at index 5 is 14
count is 2.

So for the right subarray we will go to the left and right
For left,the end index is 5-1=4
The new mid is 4+4/2=4
Element at index 4 is 14
count is 3.
As it has only one element we stop here.
For right,the start index is 5+1=6.
The new mid is 6+6/2=6
Element at index 6 is 14
count is 4.
As there is only one element we stop here.

As count=4 is greater than n/2=3 the majority element is 9.

Code for Approach 2

# include <stdio.h>
# include <stdbool.h>


int binSearch(int arr[], int low, int high, int x)
{
	if (high >= low)
	{
		int mid = (low + high)/2; /*low + (high - low)/2;*/

	
		if ( (mid == 0 || x > arr[mid-1]) && (arr[mid] == x) )
			return mid;
		else if (x > arr[mid])
			return binSearch(arr, (mid + 1), high, x);
		else
			return binSearch(arr, low, (mid -1), x);
	}

	return -1;
}


bool isMaj(int arr[], int n, int x)
{
	
	int i = binSearch(arr, 0, n-1, x);

	
	if (i == -1)
		return false;

	
	if (((i + n/2) <= (n -1)) && arr[i + n/2] == x)
		return true;
	else
		return false;
}

int main()
{
	int arr[] = {6, 9, 14, 14, 14, 14, 19};
	int n = 7;
    int mid=n/2;
    int x=arr[mid];
	if (isMaj(arr, n, x))
		printf("%d appears more than %d times in array.It is majority element",
			x, n/2);
	else
		printf("no majority element is present");
	return 0;
}

Output

14 appears more than 3 times in array.It is majority element

...Program finished with exit code 0
Press ENTER to exit console.

If no majority element is present then:

The array is 6, 9, 10, 10, 14, 14, 19

Here the size is 7
n/2=3
The element at 3 is 10.
By binary search the count of 10 is 2 which is less than 3.
Hence no majority element present.

Output

no majority element is present

...Program finished with exit code 0
Press ENTER to exit console.

Time and Space Complexity of the Approach

As we are using binary search therefore the time complexity is O(log(n)).

As no auxillary space is used the space complexity is O(1).

Approach 3: O(1) time approach

We are assuming that the most frequent element is already present. So, the majority element will always be present at the middle position as the frequency is more than half the total number of elements.

Therefore, we have to take the n/2 th element.

Lets see an example:

The array is 12, 12, 67, 67, 67, 67, 90

The size is 7
n/2=7/2=3
The element at n/2 is 67.So return 67 as majority element.

Code for Approach 3

#include <stdio.h>
#include <stdbool.h>



int main()
{
	int arr[] = { 12, 12, 67, 67, 67, 67, 90 };
	int n = 7;
	int mid =n/2;
    int x=arr[mid];
	
    printf("The majority element is %d",x);

}

Output

The majority element is 67

...Program finished with exit code 0
Press ENTER to exit console.

Time and Space Complexity of the Approach

As we are just taking the n/2 th element the time complexity is O(1).

As no auxillary space is used the space complexity is O(1).

Thus, in this article at OpenGenus we have discussed the three approaches for solving the problem for finding majority element in a sorted array.