Поиск без сортировки

«Бинарный поиск работает на отсортированном массиве» — так его обычно и запоминают. Это верно как частный случай и вредно как общее правило: половина задач на бинарный поиск не про сортированные данные вовсе.

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

Задача, которая всё объясняет

Дан массив из нулей и единиц длины $10^9$. Известно только, что $a_0 = 0$ и $a_{n-1} = 1$. Порядок внутри произвольный: нули и единицы перемешаны как угодно.

Найдите любую позицию $i$, где $a_i = 0$ и $a_{i+1} = 1$.

Массив не отсортирован. Никакой монотонности нет. И тем не менее задача решается за логарифм.

Инвариант: $a_l = 0$ и $a_r = 1$. По условию он верен изначально. Смотрим в середину: если там ноль — двигаем l, если единица — двигаем r. В обоих случаях инвариант сохранился.

int l = 0, r = n - 1;          // a[l] == 0, a[r] == 1
while (r - l > 1) {
    int m = l + (r - l) / 2;
    if (a[m] == 0) l = m; else r = m;
}
// теперь a[l] == 0, a[r] == 1, r == l + 1

Когда цикл кончается, $r = l + 1$, а инвариант всё ещё держится — значит, l и есть искомая позиция.

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

Условия $a_0 = 0$ и $a_{n-1} = 1$ существенны. Уберите любое — и инвариант неоткуда взять; без него задача честно требует $O(n)$.

Поиск пика

Дан массив, в котором нет двух равных соседей. Найдите локальный максимум — элемент, который не меньше обоих соседей (у крайних сосед один).

Массив опять не отсортирован. Но инвариант есть: держим отрезок, внутри которого пик гарантированно существует.

int l = 0, r = n - 1;
while (l < r) {
    int m = l + (r - l) / 2;
    if (a[m] < a[m + 1]) l = m + 1; else r = m;
}
// l — позиция локального максимума

Почему это верно. Если $a_m < a_{m+1}$, то на отрезке $[m+1, r]$ пик есть: последовательность там начинает расти, а расти вечно не может — либо где-то развернётся, либо упрётся в правый конец, который тоже пик. Симметрично в другую сторону.

Тот же приём — основа поиска экстремума унимодальной функции, про который отдельно в статье о тернарном поиске.

Повёрнутый отсортированный массив

Массив был отсортирован, а потом его циклически сдвинули: 4 5 6 7 1 2 3. Найдите минимум.

Инвариант: минимум лежит в полуинтервале $[l, r]$. Сравниваем середину с правым концом:

int l = 0, r = n - 1;
while (l < r) {
    int m = l + (r - l) / 2;
    if (a[m] > a[r]) l = m + 1;   // точка поворота правее
    else r = m;                   // поворот здесь или левее
}
// a[l] — минимум

Сравнение именно с правым концом, а не с левым: сравнение с a[l] даёт неоднозначность, когда массив не повёрнут вовсе. Это классическая ловушка на собеседованиях.

Если равные элементы допускаются, худший случай вырождается в $O(n)$: массив 2 2 2 1 2 не даёт понять, куда идти, и приходится сдвигать границу на единицу.

Поиск в отсортированной матрице

Матрица $n \times m$, строки возрастают слева направо, столбцы — сверху вниз. Есть ли в ней число $x$?

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

int i = 0, j = m - 1;
while (i < n && j >= 0) {
    if (a[i][j] == x) return true;
    if (a[i][j] > x) j--;   // весь столбец ниже тоже больше
    else i++;               // вся строка левее тоже меньше
}
return false;

Это $O(n + m)$, а не логарифм, но идея та же: каждый шаг отбрасывает целую строку или столбец, потому что инвариант «искомое, если есть, лежит в оставшемся прямоугольнике» сохраняется.

Как этим пользоваться

Когда в задаче видно, что перебор слишком долгий, вопрос стоит задавать не «отсортированы ли данные», а:

Могу ли я записать утверждение про l и r, которое верно вначале и остаётся верным после сдвига любой границы?

Если да — бинарный поиск применим, каким бы хаотичным ни выглядел вход. Если нет — сортировка сама по себе не поможет.

И обратное предупреждение: отсортированность не гарантирует применимость. Если предикат по массиву не монотонен — скажем, «$a_i$ делится на 7» — сортировка не сделает его монотонным, и бинарный поиск найдёт мусор.