Какво е половината на масив и как да я определим?

Половината на масива (или "медианата" на масива, ако е сортиран) е елементът, който, ако масивът е сортиран, го дели на две части: елементите по-малки или равни на медианата и елементите по-големи или равни на медианата. Ако броят на елементите е четен, медианата често се счита за аритметичната средна на двата централни елемента. В контекста на "половината на масива" в задачите за интервю може също да се подразбира търсенето на мажоритарен елемент, който се среща повече от 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 // Няма мажоритарен елемент
}

Важно е да се уточни с интервюиращия, кой точно тип "половина на масива" има предвид в контекста на задачата.