Порядок, который меняет всё

В прошлом уроке мы искали в журнале заказов [42, 17, 42, 58, 17] первое вхождение кода 42 и находили его на позиции 0. Работал линейный поиск: шли слева направо, сравнивали, возвращали при первом совпадении. Просто и надёжно, но у него есть цена — в худшем случае придётся просмотреть весь массив. Для n элементов это n сравнений. Если массив огромен, а поиск выполняется часто, линейный проход становится узким местом.

А теперь предположим, что данные упорядочены. Не как попало, а по возрастанию: скажем, коды [3, 7, 7, 12, 18, 25]. Каждый следующий элемент не меньше предыдущего. Спрашивается: помогает ли это нам искать быстрее?

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

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

Что сломается без порядка

Разберём контрпример, чтобы увидеть, что именно ломается без порядка. Пусть массив такой: [12, 3, 25, 7, 18, 7]. Он не отсортирован. Ищем 25. Берём середину — индекс 3, там 7. Сравниваем: 7 меньше 25. По логике бинарного поиска мы должны были бы заключить, что искомое находится правее, и отбросить всё, что лежит слева от середины. Но слева как раз лежит 25 — на позиции 2. Мы его только что выбросили из рассмотрения. Дальнейший поиск пойдёт по правой половине и в итоге вернёт −1, хотя значение в массиве есть. Значит, без предварительной сортировки вывод «всё слева меньше середины» неверен, и отбрасывание половины становится необоснованным.

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

Полуинтервал и середина

Теперь о формальных деталях, без которых легко ошибиться.

Будем рассматривать диапазон как полуинтервал [left, right). Это значит: позиция left входит в диапазон, позиция right — уже нет. Изначально left = 0, right = n, то есть весь массив. Полуинтервал удобен тем, что длина диапазона — это просто right − left, и пустой диапазон выражается одним условием left == right.

Середина вычисляется как mid = left + (right − left) / 2. Здесь деление целочисленное, с округлением вниз. Почему не просто (left + right) / 2? Потому что при очень больших left и right сумма может выйти за пределы типа. Формула left + (right − left) / 2 такой опасности не создаёт: сначала вычисляется разность, а она заведомо не больше n. Это не украшение, а защита от переполнения, и её стоит запомнить.

Инвариант всего алгоритма такой: если искомое значение вообще есть в массиве, то оно находится где-то в диапазоне [left, right). Пока это условие выполняется, мы имеем право сужать диапазон. Когда диапазон становится пустым — left == right, — это значит, что искомого в массиве нет.

Поиск любого совпадения

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

Логика такая. Пока left < right, вычисляем mid. Если a[mid] равен искомому — возвращаем mid, задача решена. Если a[mid] меньше искомого — искомое, если оно есть, находится правее: сдвигаем left на mid + 1. Если a[mid] больше — сужаем справа: right = mid.

Обратите внимание на асимметрию: слева мы прибавляем единицу, справа — нет. Это следствие полуинтервала. Позиция mid уже проверена и не подошла, значит, её можно исключить. Слева это делается через left = mid + 1. Справа — через right = mid, потому что right не входит в диапазон, и установка right = mid автоматически исключает позицию mid из рассмотрения. Если бы мы написали right = mid − 1, то случайно выбросили бы ещё одну позицию, которую не проверяли.

Когда left становится равным right, диапазон пуст, и мы возвращаем −1 — признак отсутствия.

using System;

int[] codes = { 3, 7, 7, 12, 18, 25 };

Console.WriteLine(BinarySearch(codes, 12));
Console.WriteLine(BinarySearch(codes, 3));
Console.WriteLine(BinarySearch(codes, 25));
Console.WriteLine(BinarySearch(codes, 9));
Console.WriteLine(BinarySearch(Array.Empty<int>(), 5));

int BinarySearch(int[] a, int target)
{
    if (a == null) throw new ArgumentNullException(nameof(a));

    int left = 0;
    int right = a.Length;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) left = mid + 1;
        else right = mid;
    }
    return -1;
}

Вывод:

3
0
5
-1
-1

Проверим найденный случай. Ищем 12. Начинаем: left = 0, right = 6, mid = 3, a[3] = 12. Совпало, возвращаем 3. Одно сравнение — и ответ готов.

Ищем 3. mid = 3, a[3] = 12 больше 3. Значит, right = 3. Диапазон [0, 3). mid = 1, a[1] = 7 больше 3. right = 1. Диапазон [0, 1). mid = 0, a[0] = 3. Совпало, возвращаем 0.

Ищем 25. mid = 3, a[3] = 12 меньше 25. left = 4. Диапазон [4, 6). mid = 5, a[5] = 25. Совпало, возвращаем 5.

Ищем 9. mid = 3, a[3] = 12 больше 9. right = 3. Диапазон [0, 3). mid = 1, a[1] = 7 меньше 9. left = 2. Диапазон [2, 3). mid = 2, a[2] = 7 меньше 9. left = 3. Теперь left == right, диапазон пуст. Возвращаем −1. Значения 9 в массиве действительно нет.

Пустой массив: left = 0, right = 0, цикл не выполняется, сразу возвращаем −1.

Дубликаты и что именно мы находим

В массиве [3, 7, 7, 12, 18, 25] значение 7 встречается дважды, на позициях 1 и 2. Что вернёт наша функция BinarySearch, если искать 7? В этом конкретном массиве она вернёт ровно 1. На первом шаге mid = 3, a[3] = 12 больше 7, и мы уходим влево, в диапазон [0, 3). Там mid = 1, a[1] = 7 — совпадение, возвращаем 1. Но это результат конкретных чисел и конкретного порядка спусков, а не гарантия. Проверим другой массив: [7, 7, 7]. mid = 1, a[1] = 7 — совпадение, возвращаем 1. Первая позиция — 0, а мы вернули 1. Значит, BinarySearch возвращает любой индекс с подходящим значением; на дубликатах это не обязательно первое вхождение.

Первая позиция с нужным значением

Поставим задачу точнее. Найти первое (самое левое) вхождение значения в отсортированный массив. Если значения нет — вернуть какую-то метку. Приём, который для этого используется, называется lower bound. Важно понимать, что lowerBound ищет не первое равное, а первую позицию, где элемент не меньше искомого. Это тоньше, чем может показаться. В отсортированном по неубыванию массиве позиция, где впервые встречается a[i] >= target, — это как раз то место, куда target встал бы, если бы его вставили. Если по этой позиции лежит именно target, оно есть, и позиция — его первое вхождение. Если лежит что-то большее или позиция вышла за массив, значит, target отсутствует. При этом lowerBound может вернуть внутренний индекс массива, даже когда значения нет: например, если target лежит между двумя соседними элементами. И только если все элементы массива меньше target, ответом становится n — длина массива.

Формально: lowerBound(a, target) возвращает минимальный индекс pos, такой что a[pos] >= target, или n, если такого pos нет.

Как именно lowerBound вычисляется бинарным поиском? Держим тот же полуинтервал [left, right). На каждом шаге смотрим a[mid]. Если a[mid] >= target — значит, mid подходит как кандидат на границу. Но, возможно, есть ещё более левая подходящая позиция. Поэтому сужаем диапазон влево: right = mid. Здесь важная тонкость. Присваивание right = mid исключает позицию mid из полуинтервала [left, right), потому что правый конец в него не входит. Но при этом mid сохраняется как возможная граница: мы помним, что где-то начиная с неё условие уже выполнено. Ответ в итоге лежит в замкнутом отрезке [left, right], и это не противоречие, потому что right — это кандидат, который ещё не отброшен, а полуинтервал — это то, что мы продолжаем исследовать. Инвариант такой: все индексы меньше left имеют a[i] < target, а все индексы, большие или равные right, имеют a[i] >= target. Когда right равно n, второе условие выполняется автоматически: индексов, больших или равных n, в массиве нет, поэтому проверять здесь нечего.

Если же a[mid] < target — эта позиция нам не подходит, и всё, что левее, тоже: сдвигаем left = mid + 1. Обратите внимание, что в этой версии мы не возвращаемся сразу при совпадении. Нам нужно не любое совпадение, а самое левое. Поэтому даже когда a[mid] равен target, мы не останавливаемся: продолжаем сужаться влево, чтобы проверить, нет ли ещё левее.

Когда цикл заканчивается, left == right, и это и есть ответ lowerBound: первая позиция, где элемент не меньше target, либо n, если такой позиции в массиве нет. Обратите внимание на формулировку: это не «первое вхождение target», а именно «первая позиция с элементом не меньше target». В частном случае, когда по этой позиции действительно лежит target, она совпадает с первым вхождением. Чтобы ответить на исходный вопрос «есть ли target в массиве и где он первый раз встречается», после lowerBound нужно проверить: pos < n и a[pos] == target. Если да — нашли первое вхождение. Если нет — target в массиве отсутствует, а pos показывает, куда он мог бы встать, если бы его вставили.

using System;

int[] codes = { 3, 7, 7, 12, 18, 25 };

Console.WriteLine(LowerBound(codes, 7));
Console.WriteLine(LowerBound(codes, 8));
Console.WriteLine(LowerBound(codes, 30));
Console.WriteLine(LowerBound(Array.Empty<int>(), 5));

int LowerBound(int[] a, int target)
{
    if (a == null) throw new ArgumentNullException(nameof(a));

    int left = 0;
    int right = a.Length;
    while (left < right)
    {
        int mid = left + (right - left) / 2;
        if (a[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left;
}

Вывод:

1
3
6
0

Проверим каждый. Ищем 7. Первая позиция с элементом не меньше 7 — это позиция 1. Там как раз 7. Значит, первое вхождение 7 стоит на позиции 1.

Ищем 8. Первая позиция с элементом не меньше 8 — это позиция 3, где стоит 12. Проверяем: a[3] == 8? Нет. Значит, значения 8 в массиве нет. Нижняя граница показывает, куда оно бы встало, если бы его вставили.

Ищем 30. Все элементы меньше 30, поэтому нижняя граница — это длина массива, 6. Позиция за пределами массива, что сигнализирует: такого значения нет и быть не может.

Пустой массив: left = 0, right = 0, цикл не выполняется, возвращаем 0. Это корректно: нижняя граница для пустого массива — ноль.

Почему размер уменьшается на каждом шаге

Здесь стоит отдельно убедиться, что цикл не зациклится и не пропустит нужную позицию. Каждый шаг сокращает диапазон [left, right): либо right становится равным mid, либо left становится равным mid + 1. В обоих случаях длина right − left строго уменьшается.

Проверим граничные случаи. Если left = 0, right = 1, то mid = 0. Если a[0] >= target, right становится 0 — диапазон пуст, выходим. Если a[0] < target, left становится 1 — снова пусто. Значит, диапазон длиной 1 всегда разрешается за один шаг. Проблема «застрять» на диапазоне длины 1, когда mid = left и обновление не меняет left, не возникает: обновление всегда сдвигает одну из границ.

Заметьте также, что в первой версии BinarySearch обновление right = mid тоже корректно, потому что мы уже проверили a[mid] и знаем, что оно не совпадает. Установка right = mid убирает позицию mid из диапазона без потери неисследованных элементов.

Стоимость

Оценим число итераций. Начальная длина диапазона равна n. Каждый шаг сокращает её примерно вдвое. Максимальное число итераций — floor(log₂ n) + 1 при n ≥ 1. Для пустого массива итераций ноль: цикл не выполняется ни разу. При растущем n асимптотика выражается как O(log(n + 1)); форма с n + 1 удобна тем, что корректно описывает и малые случаи вместе с большими. Дополнительная память — O(1): мы используем только left, right и mid, и их число не зависит от n. И ещё одно уточнение про инвариант пустоты. Условие «если искомое есть в массиве, оно находится в текущем диапазоне» относится именно к поиску равного значения, как в BinarySearch. Для lowerBound этот инвариант выглядит иначе: он говорит про границу между «меньше target» и «не меньше target», а не про наличие самого значения. Смешивать эти два инварианта не стоит.

Дополнительная память — O(1): мы используем только left, right и mid, и их число не зависит от n. Значение O(log(n + 1)) по времени опирается на допущение, что доступ к a[mid] стоит O(1) — то есть что мы работаем с последовательностью, где позиция даёт прямой доступ. Для массива это так; для связного списка — нет, и там бинарный поиск в исходном виде не работает.

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