Qu'est-ce que la moitié d'un tableau et comment la…

La moitié d’un tableau (ou la "médiane" du tableau, si celui-ci est trié) est l’élément qui, si le tableau est trié, le divise en deux parties : éléments inférieurs ou égaux à la médiane et éléments supérieurs ou égaux à la médiane. Si le nombre d’éléments est pair, la médiane est souvent la moyenne arithmétique des deux éléments centraux. Dans le contexte de "la moitié du tableau" dans les tâches d’entretien, cela peut aussi faire référence à la recherche d’un élément majoritaire, qui apparaît plus de N/2 fois, où N est le nombre d’éléments dans le tableau.

La définition de la moitié du tableau dépend du contexte :

Médiane (pour un tableau trié ou lors de la recherche du k-ième plus petit élément) :
- On trie le tableau.
- Si la taille N est impaire, la médiane est l’élément à l’indice N/2.
- Si la taille N est paire, la médiane est la moyenne arithmétique des éléments aux indices N/2 - 1 et N/2.
Élément majoritaire (qui apparaît > N/2 fois) :
- On utilise l’algorithme de vote de Boyer (algorithme de vote majoritaire de Boyer–Moore).
- On crée une variable candidate et count.
- On parcourt les éléments du tableau. Si l’élément actuel est égal à candidate, on augmente count. Sinon, si count > 0, on le diminue. Si count = 0, l’élément actuel devient le nouveau candidate, et count est mis à 1.
- Après une première passe, candidate est un potentiel élément majoritaire. Pour en être sûr, on effectue une seconde passe pour confirmer qu’il apparaît réellement plus de N/2 fois.

Exemple de détermination de la médiane (en Swift) :

// Tri pour trouver la médiane
func findMedian(in array: [Int]) -> Double? {
    guard !array.isEmpty else { return nil }

    let sortedArray = array.sorted()
    let n = sortedArray.count

    if n % 2 == 1 {
        return Double(sortedArray[n / 2])
    } else {
        return Double(sortedArray[n / 2 - 1] + sortedArray[n / 2]) / 2.0
    }
}

Exemple de détermination de l’élément majoritaire (en Swift) :

// Algorithme de vote de Boyer
func findMajorityElement(in array: [Int]) -> Int? {
    var candidate: Int? = nil
    var count = 0

    for element in array {
        if count == 0 {
            candidate = element
            count = 1
        } else if element == candidate {
            count += 1
        } else {
            count -= 1
        }
    }

    // Vérification si le candidat est réellement majoritaire
    var realCount = 0
    if let candidate = candidate {
        for element in array {
            if element == candidate {
                realCount += 1
            }
        }
        if realCount > array.count / 2 {
            return candidate
        }
    }

    return nil // Pas d’élément majoritaire
}

Il est important de clarifier avec l’intervieweur quel type précis de "moitié du tableau" est visé dans le contexte de la tâche.

Qu'est-ce que la moitié d'un tableau et comment la déterminer?