O que é metade de um array e como determiná-la?

A metade de um array (ou a "mediana" do array, se estiver ordenado) é o elemento que, se o array estiver ordenado, o divide em duas partes: elementos menores ou iguais à mediana e elementos maiores ou iguais à mediana. Se o número de elementos for par, a mediana costuma ser a média aritmética dos dois elementos centrais. No contexto de "metade do array" em tarefas de entrevistas, também pode referir-se à procura de um elemento maioritário, que aparece mais de N/2 vezes, onde N é o número de elementos no array.

A definição de metade do array depende do contexto:

1. Mediana (para um array ordenado ou ao procurar o k-ésimo menor elemento):

   • Ordenamos o array.
   • Se o tamanho N for ímpar, a mediana é o elemento no índice N/2.
   • Se o tamanho N for par, a mediana é a média aritmética dos elementos nos índices N/2 - 1 e N/2.

2. Elemento maioritário (que aparece > N/2 vezes):

   • Usamos o algoritmo de votação de Boyer (algoritmo de voto maioritário de Boyer–Moore).
   • Criamos uma variável candidate e count.
   • Percorremos os elementos do array. Se o elemento atual for igual a candidate, incrementamos count. Caso contrário, e count > 0, decrementamos count. Se count = 0, o elemento atual torna-se o novo candidate, e count é definido como 1.
   • Após a primeira passagem, candidate é um possível elemento maioritário. Para garantir, fazemos uma segunda passagem para confirmar que ele realmente aparece mais de N/2 vezes.

Exemplo de como determinar a mediana (em Swift):

// Ordenar para encontrar a 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
    }
}

Exemplo de como determinar o elemento maioritário (em Swift):

// Algoritmo de votação 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
        }
    }

    // Verificação se o candidato é realmente maioritário
    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 // Não há elemento maioritário
}

É importante esclarecer com o entrevistador qual o tipo exato de "metade do array" se pretende na questão.