## Introduction

Finding an element in a sorted array whose frequency is greater than or equal to n/2 is an **array searching problem**. It is one of the very basic problems that have many approaches. That’s why it had been asked in many interviews. It had been asked in the Microsoft, Google, Amazon, and Yahoo interview round for the role of software engineers/developers. Alongside it is one of those problems that checks an individual's critical thinking by analyzing the most fundamental approach of the programmer.

In this article, we are going to discuss two methods to solve this problem find element in a sorted array whose frequency is greater than or equal to n/2; the first is the **brute force** or naive approach, and the second is by **using** **Boyer-Moore Majority Vote Algorithm.**

Also see, __Array Implementation of Queue__ and __Rabin Karp Algorithm__

### Problem Statement

Find an element in a sorted array whose frequency is greater than or equal to n/2, in here we are given a sorted array A[] of n elements. We need to find and return the number that appears more than n/2 times.

### Sample Examples

**Example 1:**

**Input**: A[] =

**Output**:

` 3`

**Explanation**: In the above example, the total number of elements in the array is 8, and the element which is appearing more than n/2 or 8/2=4 times is 3. That’s why the output is 3.

**Example 2:**

**Input**: A[] =

**Output**:

`8`

**Explanation**: In the above example, the total number of elements in the array is 10, and the element which is appearing more than n/2 or 10/2=5 times is 8. That’s why the output is 8.

**Example 3:**

**Input**: A[] =

**Output**:

` 5`

**Explanation**: In the above example, the total number of elements in the array is 6, and the element which is appearing more than n/2 or 6/2=3 times is 5. That’s why the output is 5.

## Brute Force Approach (using nested loops)

For this problem, a simple brute force approach would be to use nested loops and count the frequency of each element. When we reach an element with a frequency greater than n/2, we have found our majority element.

### Pseudocode

```
for i = 0 to n-2
int count = 1
for j = i+1 to n-1
if A[i] is equal to A[j]
count = count + 1
if count > n/2
return A[i]
```

### Implementation

```
#include <iostream>
using namespace std;
int findMajorityElement(int A[], int n)
{
for (int i = 0;i< n-2;i++ )
{ int count = 1;
for ( int j = i+1;j< n-1;j++ )
{
if ( A[i] == A[j] )
count = count + 1;
}
if ( count > n/2 )
return A[i];
}
return -1;
}
int main()
{
int arr[] = {1,3,3,3,3,3,5,9};
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMajorityElement(arr, n);
return 0;
}
```

**Output**

`3`

#### Time complexity

The time complexity of this approach is** O(N^2)**. Since we are using nested loops and iterating each loop N time.

#### Space complexity

The space complexity of this approach is **O(1)**. Since we are not using any extra space.