Programa C++ para verificar el elemento mayoritario en una array ordenada

Pregunta: Escribe una función para encontrar si un entero x aparece más de n/2 veces en una array ordenada de n enteros. 
Básicamente, necesitamos escribir una función, digamos isMajority(), que tome una array (arr[] ), el tamaño de la array (n) y un número para buscar (x) como parámetros y devuelva verdadero si x es un elemento mayoritario (presente más de n/2 veces).

Ejemplos: 

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)

MÉTODO 1 (usando la búsqueda lineal) Busque 
linealmente la primera aparición del elemento, una vez que lo encuentre (déjelo en el índice i), verifique el elemento en el índice i + n/2. Si el elemento está presente en i+n/2, devuelve 1; de lo contrario, devuelve 0.

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

Producción: 

4 appears more than 3 times in arr[]

Complejidad de tiempo: O(n)

MÉTODO 2 (Usando la búsqueda binaria) 
Use la metodología de búsqueda binaria para encontrar la primera ocurrencia del número dado. El criterio para la búsqueda binaria es importante aquí. 

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

Producción: 

3 appears more than 3 times in arr[]

Complejidad del tiempo: O(Logn) 
Paradigma algorítmico: divide y vencerás

MÉTODO 3: Si ya se ha dado que la array está ordenada y existe un elemento mayoritario, verificar si un elemento en particular es tan fácil como verificar si el elemento central de la array es el número con el que estamos verificando.

Dado que un elemento mayoritario aparece más de n/2 veces en una array, siempre será el elemento central. Podemos usar esta lógica para verificar si el número dado es el elemento mayoritario.

#include <iostream>
using namespace std;
  
bool isMajorityElement(int arr[], int n, int key)
{
    if (arr[n / 2] == key)
        return true;
    else
        return false;
}
  
int main()
{
    int arr[] = { 1, 2, 3, 3, 3, 3, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;
    if (isMajorityElement(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

3 appears more than 3 times in arr[]

Complejidad temporal : O(1)
Espacio auxiliar: O(1)

Consulte el artículo completo sobre Comprobar el elemento mayoritario en una array ordenada para obtener más detalles.