Co je to polovina pole a jak ji určit?

Polovina pole (nebo "medián" pole, pokud je seřazené) je prvek, který pokud je pole seřazeno, dělí ho na dvě části: prvky menší nebo rovné mediánu a prvky větší nebo rovné mediánu. Pokud je počet prvků sudý, medián se často považuje za aritmetický průměr dvou středních prvků. V kontextu "poloviny pole" v úlohách pohovorů může být také míněno hledání majoritního prvku, který se vyskytuje více než N/2krát, kde N je počet prvků v poli.

Definice poloviny pole závisí na kontextu:

1. Medián (pro seřazené pole nebo při hledání k-tého nejmenšího prvku):

   • Seřadíme pole.
   • Pokud je velikost N lichá, medián je prvek na indexu N/2.
   • Pokud je velikost N sudá, medián je aritmetický průměr prvků na indexech N/2 - 1 a N/2.

2. Majoritní prvek (prvek, který se vyskytuje > N/2krát):

   • Používáme algoritmus hlasování Boyera (Boyere–Moore majority vote algorithm).
   • Vytvoříme proměnné candidate a count.
   • Procházíme prvky pole. Pokud je aktuální prvek roven candidate, zvýšíme count. Pokud ne, a count > 0, snížíme count. Pokud je count = 0, aktuální prvek se stává novým candidate a count se nastaví na 1.
   • Po prvním průchodu je candidate potenciálním majoritním prvkem. Pro jistotu je třeba provést druhý průchod, aby se ověřilo, že se skutečně vyskytuje více než N/2krát.

Příklad určení mediánu (v Swift):

// Seřazení pro nalezení mediánu
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
    }
}

Příklad určení majoritního prvku (v Swift):

// Algoritmus hlasování 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
        }
    }

    // Ověření, zda je candidate skutečně majoritním prvkem
    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 // Žádný majoritní prvek
}

Je důležité se zeptat na dotazujícího, o jaký přesně typ "poloviny pole" se v kontextu úlohy jedná.