Šta je polovina niza i kako je odrediti?

Половина масива (или "медијана" масива, ако је сортиран) је елемент који, ако је масив сортиран, дели га на две делове: елементе мање или једнаке медијани и елементе веће или једнаке медијани. Ако је број елемената паран, медијана се често сматра аритметичком средином два централна елемента. У контексту "половине масива" у задацима за интервју може се подразумевати и тражење мажоритарног елемента, који се појављује више од N/2 пута, где је N број елемената у масиву.

Дефиниција половине масива зависи од контекста:

1. Медијана (за сортиран масив или при тражењу k-тог најмањег елемента):

   • Сортирамо масив.
   • Ако је величина N непаран, медијана је елемент на индексу N/2.
   • Ако је величина N паран, медијана је аритметичка средина елемената на индексима N/2 - 1 и N/2.

2. Мажоритарни елемент (елемент који се појављује > N/2 пута):

   • Користимо алгоритам гласања Бојера (Boyer–Moore majority vote algorithm).
   • Креирамо променљиве candidate и count.
   • Прођемо кроз елементе масива. Ако је тренутни елемент једнак candidate, повећавамо count. Ако није, и count > 0, смањујемо count. Ако је count = 0, тренутни елемент постаје нови candidate, а count се поставља на 1.
   • После првог пролаза, candidate је потенцијални мажоритарни елемент. За гаранцију, потребно је извршити други пролаз како бисмо били сигурни да се заиста појављује више од N/2 пута.

Пример одређивања медијане (у Swift):

// Сортирање за проналазак медијане
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
    }
}

Пример одређивања мажоритарног елемента (у Swift):

// Алгоритам гласања Бојера
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
        }
    }

    // Провера да ли је кандидат заиста мажоритарни елемент
    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 // Нема мажоритарног елемента
}

Важно је да се појасни са интервјуером који тачно тип "половине масива" има у виду у контексту задатка.