Бинарный поиск для нахождения подходящей пары

Заметьте, что в первоначальной задаче условие на то, что сначала идут нули, а потом идут единицы несущественно. Главное, чтобы мы знали индекс, который показывает на 0, и индекс, который показывает на 1. После этого бинарным поиском мы таким же способом найдем пару соседних нуля и единицы в массиве.

Поэтому бинарный поиск работает и не для возрастающих массивов / функций, если наша задача состоит именно в поиске двух соседних индексов, в которых условие выполняется и не выполняется.

Например, если мы знаем, что $f(x_0) < 0$ и $f(x_1) > 0$, и функция непрерывная, то бинарным поиском можно найти ноль этой функции между $x_0$ и $x_1$, даже если функция не монотонная!

Или, например, если нужно в массиве найти соседние четное и нечетное числа, и известно положение какого-то четного числа и какого-то нечетного числа, то это тоже можно легко сделать с помощью бинарного поиска.

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin