# Find the majority element from the sorted array

## Given a sorted array, we need to find if a given x is a majority element.

Majority element: Number occurring more than half the size of the array.

INPUT: 1 2 2 2 4

OUTPUT: 2 IS A MAJOR ELEMENT

### Method 1

TIME COMPLEXITY: O(logN)

SPACE COMPLEXITY: O(1)

We use the concept of Binary Search but in a tricky manner. The binary search can be modified easily to check the first occurrence of the given number x.

### Algorithm

1. Check if the middle element of array is x or not .Because any majority element must be at middle of array if it occurs more than N/2 times.
2. If present then do a custom Binary Search to find the first occurrence of x.
3. The index obtained is say k,then check if  (k+N/2)th  index also has x. If yes then x is a majority element.

NOTE: Use lower_bound and higher_bound STL functions to do the task easily.

### Program for Method 1

``````#include<bits/stdc++.h>
using namespace std;

int main()
{
int arr[] = {1,2,2,2,4};
int N = sizeof(arr)/sizeof(arr[0]);
int x;

//the element to be checked for majority element
cin>>x;

int low=lower_bound(arr,arr+N,x)-arr; //index of first occurence of the element
int high=upper_bound(arr,arr+N,x)-arr; //index of the last occurenece of element

if(high-low>N/2)
cout<<x <<" is Majority element\n";
else
cout<<x <<" is not a Majority element\n";
return 0;
}``````

### Method 2

TIME COMPLEXITY: O(N)

SPACE COMPLEXITY: O(1)

### Algorithm

Loop till the half of the array doing :
a. If the present element is x then check if (the present index + N/2)th index contains x.
b. If it does then x is a majority element.
c. Else x is not a majority element.

### Program for Method 2

``````#include <bits/stdc++.h>
using namespace std;

int main()
{
int arr[] = {1,2,2,2,4};
int N = sizeof(arr)/sizeof(arr[0]);

int end;
if(N%2)
end = N/2+1;
else
end = N/2;

int x;

cin>>x; //the element to be checked for majority element

for(int i=0;i<end;i++)
{
if(arr[i] ==x and x == arr[i+N/2])
{
cout << x <<" is a mojority element "	<<endl;
return 0;
}
}

cout<<x<<" is not a majority element\n";
}``````

Scroll to Top