Encuentre el elemento en una array ordenada cuya frecuencia sea mayor o igual a n/2.

Dada una array ordenada de longitud n, encuentre el número en la array que aparece más que o igual a n/2 veces. Se da que tal elemento siempre existe.

Ejemplos: 

Input :  2 3 3 4
Output : 3

Input :  3 4 5 5 5 
Output : 5

Input : 1 1 1 2 3
Output : 1

Para encontrar ese número, recorremos la array y verificamos la frecuencia de cada elemento en la array si es mayor o igual a n/2 pero requiere espacio adicional y la complejidad del tiempo será O (n). 

Pero podemos ver que si hay un número que viene más o igual a n/2 veces en una array ordenada, entonces ese número debe estar presente en la posición n/2, es decir, a[n/2].

Implementación:

// C++ code to find majority element in a
// sorted array
#include <iostream>
using namespace std;
 
int findMajority(int arr[], int n)
{
    return arr[n / 2];
}
 
int main()
{
    int arr[] = { 1, 2, 2, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << findMajority(arr, n);
    return 0;
}

// Java code to find majority element in a
// sorted array
public class Test {
 
    public static int findMajority(int arr[], int n)
    {
        return arr[n / 2];
    }
    public static void main(String args[])
    {
        int arr[] = { 1, 2, 2, 3 };
        int n = arr.length;
        System.out.println(findMajority(arr, n));
    }
}

# Python 3 code to find
# majority element in a
# sorted array
 
def findMajority(arr, n):
 
    return arr[int(n / 2)]
 
# Driver Code
arr = [1, 2, 2, 3]
n = len(arr)
print(findMajority(arr, n))
 
# This code is contributed by Smitha.

// C# code to find majority element in a
// sorted array
using System;
 
public class GFG {
 
    public static int findMajority(int []arr, int n)
    {
        return arr[n / 2];
    }
     
    // Driver code
    public static void Main()
    {
         
        int []arr = { 1, 2, 2, 3 };
        int n = arr.Length;
         
        Console.WriteLine(findMajority(arr, n));
    }
}
 
// This code is contributed by vt_m.

<?php
// PHP code to find majority
// element in a sorted array
 
function findMajority($arr, $n)
{
    return $arr[intval($n / 2)];
}
 
    // Driver Code
    $arr = array(1, 2, 2, 3);
    $n = count($arr);
    echo findMajority($arr, $n);    
     
// This code is contributed by Sam007
?>

<script>
 
// Javascript code to find majority element in a
// sorted array
 
function findMajority(arr,  n)
{
    return arr[Math.floor(n / 2)];
}
 
// driver code
 
    let arr = [ 1, 2, 2, 3 ];
    let n = arr.length;
    document.write(findMajority(arr, n));
 
</script>

2

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

Artículos relacionados: 
elemento mayoritario en una array no ordenada  
Comprobar el elemento mayoritario en una array ordenada

Este artículo es una contribución de Amit Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.