Cos'è la metà di un array e come determinarla?

La metà di un array (o la "mediana" dell’array, se è ordinato) è l’elemento che, se l’array è ordinato, lo divide in due parti: elementi minori o uguali alla mediana e elementi maggiori o uguali alla mediana. Se il numero di elementi è pari, la mediana è spesso la media aritmetica dei due elementi centrali. Nel contesto di "la metà dell’array" nelle domande di colloquio, può anche riferirsi alla ricerca di un elemento majoritario, che si presenta più di N/2 volte, dove N è il numero di elementi nell’array.

La definizione di metà dell’array dipende dal contesto:

1. Mediana (per un array ordinato o nella ricerca del k-esimo elemento più piccolo):

   • Ordiniamo l’array.
   • Se la dimensione N è dispari, la mediana è l’elemento all’indice N/2.
   • Se la dimensione N è pari, la mediana è la media aritmetica degli elementi agli indici N/2 - 1 e N/2.

2. Elemento maggioritario (che si presenta > N/2 volte):

   • Usiamo l’algoritmo di voto di Boyer (algoritmo di voto maggioritario di Boyer–Moore).
   • Creiamo una variabile candidate e count.
   • Scorriamo gli elementi dell’array. Se l’elemento corrente è uguale a candidate, incrementiamo count. Se no, e count > 0, decrementiamo count. Se count = 0, l’elemento corrente diventa il nuovo candidate, e count viene impostato a 1.
   • Dopo il primo passaggio, candidate è un potenziale elemento maggioritario. Per essere sicuri, si effettua un secondo passaggio per verificare che effettivamente si presenti più di N/2 volte.

Esempio di determinazione della mediana (in Swift):

// Ordinare per trovare la mediana
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
    }
}

Esempio di determinazione dell’elemento maggioritario (in Swift):

// Algoritmo di voto di 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
        }
    }

    // Verifica se il candidato è effettivamente maggioritario
    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 // Nessun elemento maggioritario
}

È importante chiarire con l’intervistatore quale tipo esatto di "metà dell’array" si intende nel contesto del problema.