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

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

А теперь представьте, что есть алгоритм, который найдёт тот же товар за 23 проверки. Не 23 тысячи, не 23 сотни — ровно 23. Из десяти миллионов. Звучит неправдоподобно? На самом деле — чистая математика. И называется это бинарный поиск. Прежде чем писать код, разберём саму идею — она наверняка знакома вам из повседневной жизни.

Вспомните бумажный словарь. Вам нужно найти слово «молоко». Вы ведь не листаете словарь с первой страницы, правда? Вы открываете его примерно посередине. Видите букву «П» — значит, «М» левее. Открываете левую половину посередине — буква «К». Значит, «М» правее. Ещё одно деление — и вы уже на нужной странице. За три-четыре шага вы нашли слово в тысячестраничном словаре.

Именно так работает бинарный поиск: каждый шаг отбрасывает половину оставшихся данных.

Обратите внимание на ключевое слово — отсортированном. Это обязательное условие. Если данные не отсортированы, бинарный поиск работать не будет — он просто даст неправильный результат. Это как пытаться искать слово в словаре, где страницы перемешаны случайным образом — деление пополам ничего не даст.

Разберём алгоритм пошагово на конкретном примере. Допустим, у нас есть отсортированный массив зарплат сотрудников (в тысячах рублей), и мы ищем сотрудника с зарплатой 72:

int[] salaries = { 25, 30, 38, 45, 52, 60, 72, 85, 90, 100, 115, 130 };
// Индексы:        0   1   2   3   4   5   6   7   8   9   10   11
// Ищем: 72

Шаг 1. Берём весь массив: left = 0, right = 11. Средний индекс: mid = (0 + 11) / 2 = 5. Элемент salaries[5] = 60. Наша цель 72 больше 60 — значит, искомый элемент точно правее. Отбрасываем всю левую половину: left = 6.

Шаг 2. Теперь область поиска: индексы 6–11. Средний: mid = (6 + 11) / 2 = 8. Элемент salaries[8] = 90. Цель 72 меньше 90 — значит, искомый элемент левее. right = 7.

Шаг 3. Область: индексы 6–7. Средний: mid = (6 + 7) / 2 = 6. Элемент salaries[6] = 72. Нашли! Возвращаем индекс 6.

Три шага — и элемент найден в массиве из 12 элементов. Линейный поиск в худшем случае сделал бы 12 сравнений. Разница пока небольшая, но на больших объёмах она становится колоссальной. Теперь напишем это на C#. Начнём с итеративной версии — она проще для понимания и чаще используется на практике.

static int BinarySearch(int[] array, int target)
{
    int left = 0;
    int right = array.Length - 1;

    while (left <= right)
    {
        int mid = left + (right - left) / 2;

        if (array[mid] == target)
            return mid;          // нашли — возвращаем индекс

        if (array[mid] < target)
            left = mid + 1;      // цель правее — сдвигаем левую границу
        else
            right = mid - 1;     // цель левее — сдвигаем правую границу
    }

    return -1; // элемент не найден
}

Разберём каждую деталь.

Переменные left и right — это границы текущей области поиска. В начале мы ищем по всему массиву, поэтому left = 0 и right = array.Length - 1.

Цикл while (left <= right) продолжается, пока область поиска не пуста. Если left стал больше right — мы проверили все возможные позиции и элемента в массиве нет.

Вычисление среднего индекса: mid = left + (right - left) / 2. Казалось бы, можно написать проще: (left + right) / 2. Но тут есть подводный камень.

Дальше — три ветки сравнения. Если средний элемент равен цели — мы нашли ответ. Если средний элемент меньше цели — искомое значение может быть только правее, поэтому сдвигаем left на mid + 1. Если больше — только левее, сдвигаем right на mid - 1.

Обратите внимание: мы сдвигаем границу на mid + 1 или mid - 1, а не на mid. Сам mid мы уже проверили — нет смысла включать его в следующую итерацию. Если забыть про +1 / -1, алгоритм может зависнуть в бесконечном цикле, когда left == right.

Вызовем наш метод:

int[] salaries = { 25, 30, 38, 45, 52, 60, 72, 85, 90, 100, 115, 130 };

int index = BinarySearch(salaries, 72);
Console.WriteLine(index);   // 6

int missing = BinarySearch(salaries, 50);
Console.WriteLine(missing);  // -1

Работает: зарплата 72 найдена на позиции 6, а зарплаты 50 в массиве нет — получаем -1. Бинарный поиск можно реализовать и рекурсивно. Идея та же — делим массив пополам, но вместо цикла вызываем функцию саму из себя:

static int BinarySearchRecursive(int[] array, int target, int left, int right)
{
    if (left > right)
        return -1; // базовый случай — элемент не найден

    int mid = left + (right - left) / 2;

    if (array[mid] == target)
        return mid;

    if (array[mid] < target)
        return BinarySearchRecursive(array, target, mid + 1, right);
    else
        return BinarySearchRecursive(array, target, left, mid - 1);
}

Логика абсолютно идентична итеративной версии. Разница — в механизме повторения: вместо while метод вызывает сам себя с суженными границами. Базовый случай left > right останавливает рекурсию.

Какую версию выбрать? На практике итеративная предпочтительнее: она не расходует стек вызовов и чуть быстрее. Рекурсивная красивее с точки зрения математики и иногда удобнее для модификаций алгоритма (например, при поиске в дереве). Но для массивов — итеративная версия надёжнее.

Теперь поговорим о сложности. Почему бинарный поиск настолько быстр?

На каждом шаге мы уполовиниваем область поиска. Если в массиве n элементов, то после первого шага остаётся n/2, после второго — n/4, после третьего — n/8... Через k шагов останется n / 2^{k элементов. Поиск закончится, когда останется 1 элемент, то есть n / 2}k = 1, откуда k = log₂(n).

Вот конкретные числа, чтобы прочувствовать масштаб:

В массиве из 1 000 элементов — максимум 10 шагов.

Из 1 000 000 (миллион) — максимум 20 шагов.

Из 1 000 000 000 (миллиард) — максимум 30 шагов.

Миллиард элементов — тридцать проверок. Линейный поиск потратил бы на это миллиард проверок. Разница в 33 миллиона раз.

В C# не нужно писать бинарный поиск вручную для стандартных задач — в языке есть встроенный метод Array.BinarySearch():

int[] prices = { 150, 300, 450, 600, 750, 900, 1200 };

int index = Array.BinarySearch(prices, 600);
Console.WriteLine(index);  // 3

int notFound = Array.BinarySearch(prices, 500);
Console.WriteLine(notFound);  // отрицательное число

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

Есть перегрузки для поиска в диапазоне и с пользовательским компаратором:

// Поиск в диапазоне: от индекса 2, длина 4
int idx = Array.BinarySearch(prices, 2, 4, 750);

// Поиск строк с учётом порядка
string[] cities = { "Волгоград", "Казань", "Москва", "Самара" };
int cityIdx = Array.BinarySearch(cities, "Москва");
Console.WriteLine(cityIdx);  // 2

Ещё одна частая ловушка — применение бинарного поиска там, где данные меняются. Если вы часто добавляете и удаляете элементы, поддерживать массив отсортированным может быть дорого. В таких случаях лучше использовать SortedSet<T> или SortedList<TKey, TValue> — они хранят данные в порядке автоматически и поддерживают быстрый поиск.

Подведём итог. Бинарный поиск — мощнейший инструмент, но с одним жёстким требованием: данные должны быть отсортированы. Если это условие выполнено — вы получаете поиск за O(log n), что на практике означает мгновенный результат даже на миллиардах элементов. Если данные не отсортированы — либо сортируйте их заранее (O(n log n) один раз), либо используйте линейный поиск.

Бинарный поиск (Binary Search) — алгоритм поиска в отсортированном массиве, который на каждом шаге делит область поиска пополам, сравнивая искомое значение со средним элементом.

Обязательное условие — массив должен быть отсортирован. На неотсортированных данных бинарный поиск даёт неправильный результат.

Сложность — O(log n) по времени, O(1) по памяти (итеративная версия). В массиве из миллиарда элементов — не более 30 шагов.

Вычисление среднего индекса — безопасная формула: mid = left + (right - left) / 2, чтобы избежать переполнения.

Array.BinarySearch() — встроенный метод C#. Возвращает индекс найденного элемента или отрицательное число (побитовое дополнение позиции вставки).

Итеративная версия предпочтительнее рекурсивной на практике — не расходует стек вызовов и работает чуть быстрее.