Ce este jumătatea unui array și cum o determinăm?

Pe jumatatea unui array (sau "mediana" array-ului, dacă acesta este sortat) este elementul care, dacă array-ul este sortat, îl împarte în două părți: elemente mai mici sau egale cu mediană și elemente mai mari sau egale cu mediană. Dacă numărul de elemente este par, mediana este adesea calculată ca media aritmetică a celor două elemente centrale. În contextul "jumătății array-ului" în întrebările de interviu, se poate face referire și la căutarea unui element majoritar, care apare de mai mult de N/2 ori, unde N este numărul total de elemente din array.

Definiția jumătății array-ului depinde de context:

1. Mediana (pentru un array sortat sau la căutarea celui de-al k-lea cel mai mic element):

   • Sortăm array-ul.
   • Dacă dimensiunea N este impară, mediana este elementul de la indexul N/2.
   • Dacă dimensiunea N este pară, mediana este media aritmetică a elementelor de la indicii N/2 - 1 și N/2.

2. Elementul majoritar (care apare de mai mult de N/2 ori):

   • Folosim algoritmul de votare Boyer (algoritmul de vot majoritar Boyer–Moore).
   • Creăm o variabilă candidate și count.
   • Parcurgem elementele array-ului. Dacă elementul curent este egal cu candidate, creștem count. Dacă nu, și count > 0, scădem count. Dacă count devine 0, elementul curent devine noul candidate, iar count se setează la 1.
   • După prima trecere, candidate este un potențial element majoritar. Pentru a fi sigur, se face o a doua trecere pentru a confirma dacă acesta apare cu adevărat mai mult de N/2 ori.

Exemplu de determinare a medianei (în Swift):

// Sortare pentru găsirea medianei
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
    }
}

Exemplu de determinare a elementului majoritar (în Swift):

// Algoritmul de votare 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
        }
    }

    // Verificare dacă candidate-ul este cu adevărat elementul majoritar
    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 // Nu există element majoritar
}

Este important să clarificați cu intervievatorul ce tip exact de "jumătate a array-ului" se are în vedere în contextul problemei.