# Check for Majority Element in a sorted array

Question: Write a C function to find if a given integer x appears more than n/2 times in a sorted array of n integers.

Basically, we need to write a function say isMajority() that takes an array (arr[] ), array’s size (n) and a number to be searched (x) as parameters and returns true if x is a majority element (present more than n/2 times).

Examples:

```Input: arr[] = {1, 2, 3, 3, 3, 3, 10}, x = 3
Output: True (x appears more than n/2 times in the given array)

Input: arr[] = {1, 1, 2, 4, 4, 4, 6, 6}, x = 4
Output: False (x doesn't appear more than n/2 times in the given array)

Input: arr[] = {1, 1, 1, 2, 2}, x = 1
Output: True (x appears more than n/2 times in the given array)
```

METHOD 1 (Using Linear Search)
Linearly search for the first occurrence of the element, once you find it (let at index i), check element at index i + n/2. If element is present at i+n/2 then return 1 else return 0.

## C

 `/* C Program to check for majority element in a sorted array */` `# include ` `# include ` ` `  `bool` `isMajority(``int` `arr[], ``int` `n, ``int` `x) ` `{ ` `    ``int` `i; ` ` `  `    ``/* get last index according to n (even or odd) */` `    ``int` `last_index = n%2? (n/2+1): (n/2); ` ` `  `    ``/* search for first occurrence of x in arr[]*/` `    ``for` `(i = 0; i < last_index; i++) ` `    ``{ ` `        ``/* check if x is present and is present more than n/2 ` `           ``times */` `        ``if` `(arr[i] == x && arr[i+n/2] == x) ` `            ``return` `1; ` `    ``} ` `    ``return` `0; ` `} ` ` `  `/* Driver program to check above function */` `int` `main() ` `{ ` `     ``int` `arr[] ={1, 2, 3, 4, 4, 4, 4}; ` `     ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `     ``int` `x = 4; ` `     ``if` `(isMajority(arr, n, x)) ` `        ``printf``(``"%d appears more than %d times in arr[]"``, ` `               ``x, n/2); ` `     ``else` `        ``printf``(``"%d does not appear more than %d times in arr[]"``, ` `                ``x, n/2); ` ` `  `   ``return` `0; ` `} `

## Java

 `/* Program to check for majority element in a sorted array */` `import` `java.io.*; ` ` `  `class` `Majority { ` ` `  `    ``static` `boolean` `isMajority(``int` `arr[], ``int` `n, ``int` `x) ` `    ``{ ` `        ``int` `i, last_index = ``0``; ` ` `  `        ``/* get last index according to n (even or odd) */` `        ``last_index = (n%``2``==``0``)? n/``2``: n/``2``+``1``; ` ` `  `        ``/* search for first occurrence of x in arr[]*/` `        ``for` `(i = ``0``; i < last_index; i++) ` `        ``{ ` `            ``/* check if x is present and is present more ` `               ``than n/2 times */` `            ``if` `(arr[i] == x && arr[i+n/``2``] == x) ` `                ``return` `true``; ` `        ``} ` `        ``return` `false``; ` `    ``} ` ` `  `    ``/* Driver function to check for above functions*/` `    ``public` `static` `void` `main (String[] args) { ` `        ``int` `arr[] = {``1``, ``2``, ``3``, ``4``, ``4``, ``4``, ``4``}; ` `        ``int` `n = arr.length; ` `        ``int` `x = ``4``; ` `        ``if` `(isMajority(arr, n, x)==``true``) ` `           ``System.out.println(x+``" appears more than "``+ ` `                              ``n/``2``+``" times in arr[]"``); ` `        ``else` `           ``System.out.println(x+``" does not appear more than "``+ ` `                              ``n/``2``+``" times in arr[]"``); ` `    ``} ` `} ` `/*This article is contributed by Devesh Agrawal*/`

## Python

 `'''Python3 Program to check for majority element in a sorted array'''` ` `  `def` `isMajority(arr, n, x): ` `    ``# get last index according to n (even or odd) */ ` `    ``last_index ``=` `(n``/``/``2` `+` `1``) ``if` `n ``%` `2` `=``=` `0` `else` `(n``/``/``2``) ` ` `  `    ``# search for first occurrence of x in arr[]*/ ` `    ``for` `i ``in` `range``(last_index): ` `        ``# check if x is present and is present more than n / 2 times */ ` `        ``if` `arr[i] ``=``=` `x ``and` `arr[i ``+` `n``/``/``2``] ``=``=` `x: ` `            ``return` `1` ` `  `# Driver program to check above function */ ` `arr ``=` `[``1``, ``2``, ``3``, ``4``, ``4``, ``4``, ``4``] ` `n ``=` `len``(arr) ` `x ``=` `4` `if` `(isMajority(arr, n, x)): ` `    ``print` `(``"% d appears more than % d times in arr[]"` `                                            ``%``(x, n``/``/``2``)) ` `else``: ` `    ``print` `(``"% d does not appear more than % d times in arr[]"` `                                                    ``%``(x, n``/``/``2``)) ` ` `  ` `  `# This code is contributed by shreyanshi_arun. `

## C#

 `// C# Program to check for majority ` `// element in a sorted array  ` `using` `System; ` ` `  `class` `GFG { ` `    ``static` `bool` `isMajority(``int``[] arr,  ` `                            ``int` `n, ``int` `x) ` `    ``{ ` `        ``int` `i, last_index = 0; ` ` `  `        ``// Get last index according to ` `        ``// n (even or odd)  ` `        ``last_index = (n % 2 == 0) ? n / 2 : ` `                                    ``n / 2 + 1; ` ` `  `        ``// Search for first occurrence  ` `        ``// of x in arr[] ` `        ``for` `(i = 0; i < last_index; i++) { ` `            ``// Check if x is present and  ` `            ``// is present more than n/2 times  ` `            ``if` `(arr[i] == x && arr[i + n / 2] == x) ` `                ``return` `true``; ` `        ``} ` `        ``return` `false``; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int``[] arr = { 1, 2, 3, 4, 4, 4, 4 }; ` `        ``int` `n = arr.Length; ` `        ``int` `x = 4; ` `        ``if` `(isMajority(arr, n, x) == ``true``) ` `            ``Console.Write(x + ``" appears more than "` `+  ` `                            ``n / 2 + ``" times in arr[]"``); ` `        ``else` `            ``Console.Write(x + ``" does not appear more than "` `+  ` `                             ``n / 2 + ``" times in arr[]"``); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

## PHP

 ` `

Output :

`4 appears more than 3 times in arr[]`

Time Complexity : O(n)

METHOD 2 (Using Binary Search)
Use binary search methodology to find the first occurrence of the given number. The criteria for binary search is important here.

## C

 `/* Program to check for majority element in a sorted array */` `# include ` `# include ` ` `  `/* If x is present in arr[low...high] then returns the index of ` `first occurrence of x, otherwise returns -1 */` `int` `_binarySearch(``int` `arr[], ``int` `low, ``int` `high, ``int` `x); ` ` `  `/* This function returns true if the x is present more than n/2 ` `times in arr[] of size n */` `bool` `isMajority(``int` `arr[], ``int` `n, ``int` `x) ` `{ ` `    ``/* Find the index of first occurrence of x in arr[] */` `    ``int` `i = _binarySearch(arr, 0, n-1, x); ` ` `  `    ``/* If element is not present at all, return false*/` `    ``if` `(i == -1) ` `        ``return` `false``; ` ` `  `    ``/* check if the element is present more than n/2 times */` `    ``if` `(((i + n/2) <= (n -1)) && arr[i + n/2] == x) ` `        ``return` `true``; ` `    ``else` `        ``return` `false``; ` `} ` ` `  `/* If x is present in arr[low...high] then returns the index of ` `first occurrence of x, otherwise returns -1 */` `int` `_binarySearch(``int` `arr[], ``int` `low, ``int` `high, ``int` `x) ` `{ ` `    ``if` `(high >= low) ` `    ``{ ` `        ``int` `mid = (low + high)/2; ``/*low + (high - low)/2;*/` ` `  `        ``/* Check if arr[mid] is the first occurrence of x. ` `            ``arr[mid] is first occurrence if x is one of the following ` `            ``is true: ` `            ``(i) mid == 0 and arr[mid] == x ` `            ``(ii) arr[mid-1] < x and arr[mid] == x ` `        ``*/` `        ``if` `( (mid == 0 || x > arr[mid-1]) && (arr[mid] == x) ) ` `            ``return` `mid; ` `        ``else` `if` `(x > arr[mid]) ` `            ``return` `_binarySearch(arr, (mid + 1), high, x); ` `        ``else` `            ``return` `_binarySearch(arr, low, (mid -1), x); ` `    ``} ` ` `  `    ``return` `-1; ` `} ` ` `  `/* Driver program to check above functions */` `int` `main() ` `{ ` `    ``int` `arr[] = {1, 2, 3, 3, 3, 3, 10}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``int` `x = 3; ` `    ``if` `(isMajority(arr, n, x)) ` `        ``printf``(``"%d appears more than %d times in arr[]"``, ` `               ``x, n/2); ` `    ``else` `        ``printf``(``"%d does not appear more than %d times in arr[]"``, ` `               ``x, n/2); ` `    ``return` `0; ` `} `

## Java

 `/* Program to check for majority element in a sorted array */` `import` `java.io.*; ` ` `  `class` `Majority { ` ` `  `    ``/* If x is present in arr[low...high] then returns the index of ` `        ``first occurrence of x, otherwise returns -1 */` `    ``static` `int`  `_binarySearch(``int` `arr[], ``int` `low, ``int` `high, ``int` `x) ` `    ``{ ` `        ``if` `(high >= low) ` `        ``{ ` `            ``int` `mid = (low + high)/``2``;  ``/*low + (high - low)/2;*/` ` `  `            ``/* Check if arr[mid] is the first occurrence of x. ` `                ``arr[mid] is first occurrence if x is one of the following ` `                ``is true: ` `                ``(i)  mid == 0 and arr[mid] == x ` `                ``(ii) arr[mid-1] < x and arr[mid] == x ` `            ``*/` `            ``if` `( (mid == ``0` `|| x > arr[mid-``1``]) && (arr[mid] == x) ) ` `                ``return` `mid; ` `            ``else` `if` `(x > arr[mid]) ` `                ``return` `_binarySearch(arr, (mid + ``1``), high, x); ` `            ``else` `                ``return` `_binarySearch(arr, low, (mid -``1``), x); ` `        ``} ` ` `  `        ``return` `-``1``; ` `    ``} ` ` `  ` `  `    ``/* This function returns true if the x is present more than n/2 ` `        ``times in arr[] of size n */` `    ``static` `boolean` `isMajority(``int` `arr[], ``int` `n, ``int` `x) ` `    ``{ ` `        ``/* Find the index of first occurrence of x in arr[] */` `        ``int` `i = _binarySearch(arr, ``0``, n-``1``, x); ` ` `  `        ``/* If element is not present at all, return false*/` `        ``if` `(i == -``1``) ` `            ``return` `false``; ` ` `  `        ``/* check if the element is present more than n/2 times */` `        ``if` `(((i + n/``2``) <= (n -``1``)) && arr[i + n/``2``] == x) ` `            ``return` `true``; ` `        ``else` `            ``return` `false``; ` `    ``} ` ` `  `    ``/*Driver function to check for above functions*/` `    ``public` `static` `void` `main (String[] args)  { ` ` `  `        ``int` `arr[] = {``1``, ``2``, ``3``, ``3``, ``3``, ``3``, ``10``}; ` `        ``int` `n = arr.length; ` `        ``int` `x = ``3``; ` `        ``if` `(isMajority(arr, n, x)==``true``) ` `            ``System.out.println(x + ``" appears more than "``+ ` `                              ``n/``2` `+ ``" times in arr[]"``); ` `        ``else` `            ``System.out.println(x + ``" does not appear more than "` `+ ` `                              ``n/``2` `+ ``" times in arr[]"``); ` `    ``} ` `} ` `/*This code is contributed by Devesh Agrawal*/`

## Python

 `'''Python3 Program to check for majority element in a sorted array'''` ` `  `# This function returns true if the x is present more than n / 2 ` `# times in arr[] of size n */ ` `def` `isMajority(arr, n, x): ` `     `  `    ``# Find the index of first occurrence of x in arr[] */ ` `    ``i ``=` `_binarySearch(arr, ``0``, n``-``1``, x) ` ` `  `    ``# If element is not present at all, return false*/ ` `    ``if` `i ``=``=` `-``1``: ` `        ``return` `False` ` `  `    ``# check if the element is present more than n / 2 times */ ` `    ``if` `((i ``+` `n``/``/``2``) <``=` `(n ``-``1``)) ``and` `arr[i ``+` `n``/``/``2``] ``=``=` `x: ` `        ``return` `True` `    ``else``: ` `        ``return` `False` ` `  `# If x is present in arr[low...high] then returns the index of ` `# first occurrence of x, otherwise returns -1 */ ` `def` `_binarySearch(arr, low, high, x): ` `    ``if` `high >``=` `low: ` `        ``mid ``=` `(low ``+` `high)``/``/``2` `# low + (high - low)//2; ` ` `  `        ``''' Check if arr[mid] is the first occurrence of x. ` `            ``arr[mid] is first occurrence if x is one of the following ` `            ``is true: ` `            ``(i) mid == 0 and arr[mid] == x ` `            ``(ii) arr[mid-1] < x and arr[mid] == x'''` `         `  `        ``if` `(mid ``=``=` `0` `or` `x > arr[mid``-``1``]) ``and` `(arr[mid] ``=``=` `x): ` `            ``return` `mid ` `        ``elif` `x > arr[mid]: ` `            ``return` `_binarySearch(arr, (mid ``+` `1``), high, x) ` `        ``else``: ` `            ``return` `_binarySearch(arr, low, (mid ``-``1``), x) ` `    ``return` `-``1` ` `  ` `  `# Driver program to check above functions */ ` `arr ``=` `[``1``, ``2``, ``3``, ``3``, ``3``, ``3``, ``10``] ` `n ``=` `len``(arr) ` `x ``=` `3` `if` `(isMajority(arr, n, x)): ` `    ``print` `(``"% d appears more than % d times in arr[]"` `                                            ``%` `(x, n``/``/``2``)) ` `else``: ` `    ``print` `(``"% d does not appear more than % d times in arr[]"` `                                                    ``%` `(x, n``/``/``2``)) ` ` `  `# This code is contributed by shreyanshi_arun. `

## C#

 `// C# Program to check for majority ` `// element in a sorted array */ ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// If x is present in arr[low...high] ` `    ``// then returns the index of first ` `    ``// occurrence of x, otherwise returns -1  ` `    ``static` `int` `_binarySearch(``int``[] arr, ``int` `low, ` `                               ``int` `high, ``int` `x) ` `    ``{ ` `        ``if` `(high >= low) { ` `            ``int` `mid = (low + high) / 2;  ` `            ``//low + (high - low)/2; ` ` `  `            ``// Check if arr[mid] is the first  ` `            ``// occurrence of x.    arr[mid] is  ` `            ``// first occurrence if x is one of  ` `            ``// the following is true: ` `            ``// (i) mid == 0 and arr[mid] == x ` `            ``// (ii) arr[mid-1] < x and arr[mid] == x ` `             `  `            ``if` `((mid == 0 || x > arr[mid - 1]) && ` `                                 ``(arr[mid] == x)) ` `                ``return` `mid; ` `            ``else` `if` `(x > arr[mid]) ` `                ``return` `_binarySearch(arr, (mid + 1), ` `                                           ``high, x); ` `            ``else` `                ``return` `_binarySearch(arr, low, ` `                                      ``(mid - 1), x); ` `        ``} ` ` `  `        ``return` `-1; ` `    ``} ` ` `  `    ``// This function returns true if the x is ` `    ``// present more than n/2 times in arr[]  ` `    ``// of size n  ` `    ``static` `bool` `isMajority(``int``[] arr, ``int` `n, ``int` `x) ` `    ``{ ` `         `  `        ``// Find the index of first occurrence ` `        ``// of x in arr[]  ` `        ``int` `i = _binarySearch(arr, 0, n - 1, x); ` ` `  `        ``// If element is not present at all, ` `        ``// return false ` `        ``if` `(i == -1) ` `            ``return` `false``; ` ` `  `        ``// check if the element is present  ` `        ``// more than n/2 times  ` `        ``if` `(((i + n / 2) <= (n - 1)) && ` `                                ``arr[i + n / 2] == x) ` `            ``return` `true``; ` `        ``else` `            ``return` `false``; ` `    ``} ` ` `  `    ``//Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` ` `  `        ``int``[] arr = { 1, 2, 3, 3, 3, 3, 10 }; ` `        ``int` `n = arr.Length; ` `        ``int` `x = 3; ` `        ``if` `(isMajority(arr, n, x) == ``true``) ` `           ``Console.Write(x + ``" appears more than "` `+ ` `                             ``n / 2 + ``" times in arr[]"``); ` `        ``else` `           ``Console.Write(x + ``" does not appear more than "` `+ ` `                             ``n / 2 + ``" times in arr[]"``); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

Output:

`3 appears more than 3 times in arr[]`

Time Complexity:
O(Logn)
Algorithmic Paradigm: Divide and Conquer

Please write comments if you find any bug in the above program/algorithm or a better way to solve the same problem.

This article is attributed to GeeksforGeeks.org

code

load comments