Бинарный поиск для нахождения подходящей пары: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «Заметьте, что в первоначальной задаче условие на то, что сначала идут нули, а потом идут е...»)
 
 
Строка 6: Строка 6:
  
 
Или, например, если нужно в массиве найти соседние четное и нечетное числа, и известно положение какого-то четного числа и какого-то нечетного числа, то это тоже можно легко сделать с помощью бинарного поиска.
 
Или, например, если нужно в массиве найти соседние четное и нечетное числа, и известно положение какого-то четного числа и какого-то нечетного числа, то это тоже можно легко сделать с помощью бинарного поиска.
 +
 +
{{Автор|Глеб Лобанов|glebodin}}

Текущая версия на 16:21, 26 сентября 2019

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

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

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

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



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

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