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

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