## 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";
}
```