Check for Majority Element in a sorted array

Last Updated : 23 Jul, 2025

Given an array arr of N elements, A majority element in an array arr of size N is an element that appears more than N/2 times in the array. The task is 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 the element at index i + n/2. If the 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<bits/stdc++.h> using namespace std; 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 code */ int main() {  int arr[] ={1, 2, 3, 4, 4, 4, 4};  int n = sizeof(arr)/sizeof(arr[0]);  int x = 4;  if (isMajority(arr, n, x))  cout << x <<" appears more than "<<  n/2 << " times in arr[]"<< endl;  else  cout <<x <<" does not appear more than" << n/2 <<" times in arr[]" << endl; return 0; } // This code is contributed by shivanisinghss2110

/* C Program to check for majority element in a sorted array */ # include <stdio.h> # include <stdbool.h> 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[0]);  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*/

Python3

'''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# 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

JavaScript

<script>  // Javascript Program to check for majority  // element in a sorted array    function isMajority(arr, n, x)  {  let i, last_index = 0;    // Get last index according to  // n (even or odd)  last_index = (n % 2 == 0) ?  parseInt(n / 2, 10) : parseInt(n / 2, 10) + 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 +   parseInt(n / 2, 10)] == x)  return true;  }  return false;  }    let arr = [ 1, 2, 3, 4, 4, 4, 4 ];  let n = arr.length;  let x = 4;  if (isMajority(arr, n, x) == true)  document.write(x + " appears more than " +   parseInt(n / 2, 10) + " times in arr[]");  else  document.write(x + " does not appear more than " +   parseInt(n / 2, 10) + " times in arr[]");   </script>

PHP

<?php // PHP Program to check for  // majority element in a  // sorted array  // function returns majority // element in a sorted array  function isMajority($arr, $n, $x) { $i; // get last index according // to n (even or odd)  $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 Code $arr = array(1, 2, 3, 4, 4, 4, 4); $n = sizeof($arr); $x = 4; if (isMajority($arr, $n, $x)) echo $x, " appears more than " , floor($n / 2), " times in arr[]"; else echo $x, "does not appear more than " , floor($n / 2), "times in arr[]"; // This code is contributed by Ajit ?>

Output

4 appears more than 3 times in arr[]

Time Complexity: O(n)
Auxiliary Space: O(1)

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++

// C++ program to check for majority // element in a sorted array  #include<bits/stdc++.h> using namespace std; // 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 code int main() {  int arr[] = { 1, 2, 3, 3, 3, 3, 10 };  int n = sizeof(arr) / sizeof(arr[0]);  int x = 3;    if (isMajority(arr, n, x))  cout << x << " appears more than "  << n / 2 << " times in arr[]"  << endl;  else  cout << x << " does not appear more than"  << n / 2 << " times in arr[]" << endl;    return 0; } // This code is contributed by shivanisinghss2110

/* C Program to check for majority element in a sorted array */ # include <stdio.h> # include <stdbool.h> /* 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[0]);  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

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

Python3

'''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# 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

JavaScript

<script>  // Javascript Program to check for majority  // element in a sorted array */    // If x is present in arr[low...high]  // then returns the index of first  // occurrence of x, otherwise returns -1  function _binarySearch(arr, low, high, x)  {  if (high >= low) {  let mid = parseInt((low + high) / 2, 10);  //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  function isMajority(arr, n, x)  {    // Find the index of first occurrence  // of x in arr[]  let 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 + parseInt(n / 2, 10)) <= (n - 1)) && arr[i + parseInt(n / 2, 10)] == x)  return true;  else  return false;  }    let arr = [ 1, 2, 3, 3, 3, 3, 10 ];  let n = arr.length;  let x = 3;  if (isMajority(arr, n, x) == true)  document.write(x + " appears more than " + parseInt(n / 2, 10) + " times in arr[]");  else  document.write(x + " does not appear more than " + parseInt(n / 2, 10) + " times in arr[]");   </script>