Массив — самая простая структура данных: пронумерованные ячейки, лежащие в памяти подряд. С него удобно начинать, потому что на нём видны все главные компромиссы сразу: что-то массив делает молниеносно, а что-то — медленно. А заодно на массиве проще всего понять, как вообще измеряют скорость алгоритмов — через O-нотацию. Если ещё не читали вводную статью раздела, загляните туда за общими терминами.

Что массив умеет и что нет

У массива есть одно суперумение: доступ по индексу за один шаг. Если известно, что нужный элемент лежит в ячейке 5, программа берёт его мгновенно, не пробегая остальные, — потому что адрес ячейки вычисляется по индексу напрямую.

А вот с остальными операциями сложнее:

  • Вставка в конец — быстрая: положили значение в первую свободную ячейку.
  • Поиск по значению — медленный: если мы не знаем индекс, приходится проверять ячейки одну за другой.
  • Удаление — медленное: после того как элемент убрали, остаётся «дыра», и следующие элементы приходится сдвигать, чтобы её закрыть.

Ещё у обычного массива фиксированный размер: сколько ячеек выделили, столько и есть. Уже отсюда виден характер массива — быстрый доступ по индексу, но неповоротливый поиск и удаление.

Упорядоченный массив

Массив можно держать отсортированным: элемент с наименьшим значением в ячейке 0, дальше по возрастанию. За это приходится платить при вставке — новый элемент нельзя просто бросить в конец, надо найти ему место и сдвинуть всех, кто больше. Зато взамен мы получаем радикально более быстрый поиск. Разберём, почему.

Линейный поиск

Простейший способ найти элемент — линейный поиск: идём с начала и сравниваем каждую ячейку с искомым значением, пока не найдём или не дойдём до конца. В упорядоченном массиве есть маленький бонус: как только встретили значение больше искомого, дальше искать бессмысленно — можно остановиться. Но в среднем всё равно приходится проверить половину массива. На миллионе элементов это до полумиллиона сравнений — медленно.

Двоичный поиск

В упорядоченном массиве работает куда более быстрый двоичный поиск. Его логика — как в детской игре «угадай число»: один загадывает число от 1 до 100, второй угадывает, а первый отвечает «больше» или «меньше».

Как угадать за минимум попыток? Называть середину оставшегося диапазона. Первый вопрос — 50. «Меньше» → число в диапазоне 1–49, следующий вопрос — 25. «Больше» → диапазон 26–49, следующий — 37. Каждая попытка делит диапазон пополам, поэтому число от 1 до 100 угадывается максимум за 7 попыток, а не за 100.

Двоичный поиск делает ровно это с массивом. Мы держим границы диапазона, где может лежать элемент, смотрим на средний элемент и по сравнению с искомым отбрасываем половину:

int binarySearch(long[] a, long key) {
    int lower = 0;
    int upper = a.length - 1;
    while (lower <= upper) {
        int mid = (lower + upper) / 2;
        if (a[mid] == key) return mid;
        else if (a[mid] < key) lower = mid + 1;
        else upper = mid - 1;
    }
    return -1;
}

Каждый проход цикла отсекает половину оставшихся элементов. Поэтому поиск в 100 элементах — около 7 сравнений, в 1000 — около 10, в миллионе — около 20. Сравните с линейным поиском: 500 000 против 20 на миллионе. Это огромная разница, и она — весь смысл держать массив упорядоченным.

Компромисс упорядоченного массива

Итак, за быстрый поиск упорядоченный массив расплачивается медленной вставкой (надо сдвигать элементы, освобождая место) и по-прежнему медленным удалением. Вывод практический:

  • упорядоченный массив хорош, когда поиск выполняется часто, а вставки и удаления редки. Пример — справочник сотрудников: читают и ищут постоянно, а нанимают и увольняют редко;
  • упорядоченный массив плох, когда вставки и удаления идут потоком. Пример — складской учёт, где товары приходят и уходят каждую минуту.

Это первый пример главного принципа раздела: структуру выбирают под то, какие операции у вас частые.

Логарифмы и O-нотация

Мы сказали «около 20 сравнений на миллионе». Откуда это число? Двоичный поиск делит диапазон пополам, пока не останется один элемент, а число делений пополам, за которое из N получается 1, — это логарифм N по основанию 2. Для миллиона log₂(1 000 000) ≈ 20. Логарифм растёт очень медленно: данные выросли в тысячу раз, а число шагов — всего в два-три раза.

Чтобы говорить о скорости, не привязываясь к конкретному железу и не считая секунды, используют O-нотацию. Она описывает, как растёт число операций с ростом объёма данных N, отбрасывая всё несущественное. Три случая, которые уже встретились:

  • O(1) — постоянное время. Число шагов не зависит от N. Такова вставка в конец неупорядоченного массива и доступ по индексу: хоть десять элементов, хоть миллион — один шаг.
  • O(N) — линейное время. Число шагов растёт пропорционально N. Таков линейный поиск: вдвое больше данных — вдвое больше работы.
  • O(log N) — логарифмическое время. Число шагов растёт как логарифм N, то есть очень медленно. Таков двоичный поиск.

O-нотацию читают как «порядок роста». O(1) лучше O(log N), а O(log N) намного лучше O(N) на больших данных. Константы и мелкие детали в ней отбрасывают: важно не «в полтора раза быстрее», а как алгоритм ведёт себя, когда данных становится очень много. Эта мерка будет сопровождать нас во всём разделе — по ней сравнивают все структуры и алгоритмы.

Почему не только массивы

Если упорядоченный массив так быстро ищет, зачем вообще остальные структуры? Из-за той самой платы: вставка и удаление у него O(N), а размер фиксирован. Как только в задаче много вставок и удалений, массив становится узким местом. Дальше в разделе мы увидим структуры, которые ищут почти так же быстро, но при этом быстро вставляют и удаляют — связанные списки, деревья, хеш-таблицы. За удобство они расплачиваются сложностью устройства.

Коротко

  • Массив мгновенно берёт элемент по индексу (O(1)), но медленно ищет по значению и медленно удаляет (O(N)).
  • Упорядоченный массив позволяет двоичный поиск — деление диапазона пополам, O(log N): на миллионе элементов около 20 шагов вместо полумиллиона.
  • Платит за это медленной вставкой: элементы приходится сдвигать. Хорош, когда поиск частый, а вставки/удаления редки.
  • O-нотация описывает, как растёт число операций с объёмом данных: O(1) — постоянно, O(log N) — очень медленно, O(N) — пропорционально. Это общая мерка скорости для всего раздела.

Дальше — простая сортировка: три способа упорядочить массив и как их сравнивают по той же O-нотации.