Problème — Élément majoritaire

on coupe le tableau en deux moitiés. Si un élément est majoritaire dans le tableau entier, il l'est nécessairement dans au moins l'une des deux moitiés. On résout donc récursivement à gauche et à droite, puis on vérifie par comptage lequel des deux candidats est réellement majoritaire sur l'ensemble.

def compte(tab, x, g, d):
    return sum(1 for k in range(g, d + 1) if tab[k] == x)

def majoritaire(tab, g, d):
    if g == d:                       # cas de base
        return tab[g]
    m = (g + d) // 2
    cand_g = majoritaire(tab, g, m)
    cand_d = majoritaire(tab, m + 1, d)
    if cand_g == cand_d:
        return cand_g
    # on compare les comptages des deux candidats
    taille = d - g + 1
    if compte(tab, cand_g, g, d) > taille // 2:
        return cand_g
    if compte(tab, cand_d, g, d) > taille // 2:
        return cand_d
    return None                      # pas de majoritaire

def element_majoritaire(tab):
    return majoritaire(tab, 0, len(tab) - 1)

La relation de récurrence $C(n)=2C(n/2)+O(n)$ donne une complexité en $O(n\log n)$, meilleure que l'approche naïve en $O(n^2)$ qui compterait chaque élément.