Given a sorted array, we need to find the majority element from the sorted array. Majority element: Number occurring more than half the size of the array. Here we have given a number x we have to check it is the majority_element or not.

## Example

**Input**

5 2

1 2 2 2 4

**Output**

2 is a majority element

**Approach 1 for finding Majority Element**

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.

**C++ Program for finding Majority Element**

#include<bits/stdc++.h> using namespace std; int main() { int n,x; cin>>n>>x; int arr[n]; for(int i=0;i<n;i++) { cin>>arr[i]; } 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 a majority element\n"; else cout<<x <<" is not a majority element\n"; return 0; }

5 2 1 2 2 2 4

2 is a majority element

### Complexity Analysis

**Time Complexity:** O(logN) because we use the concept of binary search and we know that the binary search algorithm has O(long) time complexity.

**Space Complexity:** O(1) because we just use some variables which come under O(1) or constant space complexity.

**Approach 2 for finding Majority Element**

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

**C++ Program for finding Majority Element**

#include <bits/stdc++.h> using namespace std; int main() { int N,x; cin>>N>>x; int arr[N]; for(int i=0;i<N;i++) { cin>>arr[i]; } int end; if(N%2) end = N/2+1; else end = N/2; 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"; }

5 2 1 2 3 3 6

2 is not a majority element

### Complexity Analysis

**Time Complexity****:** O(N) because we just traverse the half sub-array which is lead us to O(n) time complexity.

**Space Complexity:** O(1) because here we don’t use any auxiliary space.