Что такое половина массива и как ее определить?

Половина массива (или "медиана" массива, если он отсортирован) — это элемент, который, если массив отсортирован, делит его на две части: элементы меньше или равные медиане и элементы больше или равные медиане. Если количество элементов четное, медианой часто считают среднее арифметическое двух центральных элементов. В контексте "половины массива" в задачах собеседований может подразумеваться также поиск мажоритарного элемента, который встречается более 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
        }
    }

    // Проверка, действительно ли candidate является мажоритарным элементом
    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 // Нет мажоритарного элемента
}

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