¿Qué es la mitad de un array y cómo se determina?

La mitad de un array (o la "mediana" del array, si está ordenado) es el elemento que, si el array está ordenado, lo divide en dos partes: elementos menores o iguales a la mediana y elementos mayores o iguales a la mediana. Si el número de elementos es par, la mediana suele ser el promedio de los dos elementos centrales. En el contexto de "la mitad del array" en tareas de entrevistas, también puede referirse a la búsqueda de un elemento mayoritario, que aparece más de N/2 veces, donde N es el número de elementos en el array.

La definición de la mitad del array depende del contexto:

1. Mediana (para un array ordenado o al buscar el k-ésimo elemento más pequeño):

   • Ordenamos el array.
   • Si el tamaño N es impar, la mediana es el elemento en el índice N/2.
   • Si el tamaño N es par, la mediana es el promedio de los elementos en los índices N/2 - 1 y N/2.

2. Elemento mayoritario (que aparece > N/2 veces):

   • Usamos el algoritmo de votación de Boyer (algoritmo de voto mayoritario de Boyer–Moore).
   • Creamos una variable candidate y count.
   • Recorremos los elementos del array. Si el elemento actual es igual a candidate, incrementamos count. Si no, y count > 0, decrementamos count. Si count = 0, el elemento actual se convierte en el nuevo candidate, y count se establece en 1.
   • Después de la primera pasada, candidate es un posible elemento mayoritario. Para garantizarlo, se realiza una segunda pasada para confirmar que realmente aparece más de N/2 veces.

Ejemplo de cómo determinar la mediana (en Swift):

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

Ejemplo de cómo determinar el elemento mayoritario (en Swift):

// Algoritmo de votación 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
        }
    }

    // Verificar si el candidato es realmente mayoritario
    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 // No hay elemento mayoritario
}

Es importante aclarar con el entrevistador qué tipo exacto de "mitad del array" se tiene en mente en el contexto de la tarea.