Check for Majority Element in a sorted array

Last Updated : 21 Dec, 2023

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

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

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

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

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

Output

3 appears more than 3 times in arr[]

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

Algorithmic Paradigm: Divide and Conquer

Suggest improvement

Find a peak element which is not smaller than its neighbours

K-th Element of Two Sorted Arrays

Share your thoughts in the comments

Some standard Divide and Conquer Algorithms

Binary Search based problems

Some practice problems on Divide and Conquer algorithm

Some standard Divide and Conquer Algorithms

Binary Search based problems

Some practice problems on Divide and Conquer algorithm

Check for Majority Element in a sorted array

C++

C

Java

Python3

C#

Javascript

PHP

C++

C

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?