Czym jest połowa tablicy i jak ją określić?

Połowa tablicy (lub "mediana" tablicy, jeśli jest posortowana) to element, który, jeśli tablica jest posortowana, dzieli ją na dwie części: elementy mniejsze lub równe medianie i elementy większe lub równe medianie. Jeśli liczba elementów jest parzysta, mediana jest często średnią arytmetyczną dwóch środkowych elementów. W kontekście "połowy tablicy" w zadaniach rekrutacyjnych może również chodzić o poszukiwanie elementu większościowego, który występuje więcej niż N/2 razy, gdzie N to liczba elementów w tablicy.

Definicja połowy tablicy zależy od kontekstu:

1. Mediana (dla posortowanej tablicy lub podczas wyszukiwania k-tego najmniejszego elementu):

   • Sortujemy tablicę.
   • Jeśli rozmiar N jest nieparzysty, mediana to element na indeksie N/2.
   • Jeśli rozmiar N jest parzysty, mediana to średnia arytmetyczna elementów na indeksach N/2 - 1 i N/2.

2. Element większościowy (który występuje > N/2 razy):

   • Używamy algorytmu głosowania Boyera (algorytmu głosowania większościowego Boyer–Moore).
   • Tworzymy zmienną candidate i count.
   • Przechodzimy przez elementy tablicy. Jeśli bieżący element jest równy candidate, zwiększamy count. Jeśli nie, i count > 0, zmniejszamy count. Jeśli count = 0, bieżący element staje się nowym candidate, a count ustawiamy na 1.
   • Po pierwszym przejściu candidate jest potencjalnym elementem większościowym. Aby to potwierdzić, wykonujemy drugie przejście, aby upewnić się, że rzeczywiście występuje on więcej niż N/2 razy.

Przykład wyznaczania mediany (w Swift):

// Sortowanie w celu znalezienia mediany
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
    }
}

Przykład wyznaczania elementu większościowego (w Swift):

// Algorytm głosowania Boyera
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
        }
    }

    // Sprawdzenie, czy kandydat jest rzeczywiście elementem większościowym
    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 // Brak elementu większościowego
}

Ważne jest, aby wyjaśnić z osobą przeprowadzającą rozmowę, jaki dokładnie typ "połowy tablicy" ma na myśli w kontekście zadania.