Классический пример - поиск в массиве \(a\) какого-то элемента. При этом мы знаем какое-то \(v = a_i\) и нам нужно найти его позицию (индекс) в массиве.
В голову сразу же приходит банальное решение просто перебрать все элементы от самого первого, до последнего. Логично, что сложность алгоритма будет \(O(n)\). По идее этот алгоритм никак нельзя ускорить, но давайте предположим частный случай: массив упорядочен. Для нас неважно, как он упорядочен по возрастанию или по убыванию. В математике такое свойство называется монотонностью.
Кажется, что это ничего не меняет, но теперь мы можем применить такой прием, как бинарный поиск (бп/бинпоиск и т.п.)
Пусть массив возрастает. Возьмем участок массива от \(l\) до \(r\). Допустим мы знаем, что искомый элемент находится внутри этого подоотрезка. При обычном поиске мы просто сдвигаем \(l\) на \(1\) вправо, а \(r = n\).
Давайте возьмем \( \lfloor \frac{l+r}2 \rfloor \)-й элемент (это элемент в середине \([l;r]\)) и сравним его с искомым. Если он меньше чем искомый, значит до него точно нет искомого (массив возрастает). Если он же, напротив, больше, то после этого элемента также нет искомого.
Т.е. мы можем обновить наши \(l\) и \(r\). Таким образом, мы за каждую итерацию сужаем наш круг поиска в \(2\) раза. В худшем случае мы будем сужать интервал столько же раз, сколько возможно поделить \(n\) пополам. \(2^x = n\), где \(\lceil x\rceil\) - асимптотика нашего алгоритма. Проще говоря асимптотика бинарного поиска равна \(O(\log{n}) \), столько раз максимум мы можем поделить n пополам.
Так как алгоритм простой, то и реализация его не затрудительная, главное - внимательно следить за интервалами, иначе алгоритм зациклиться
int l = 0, r = n; // мы ищем значение на полуинтервале [l;r)
int v; // Искомое значение
while( l+1 < r) {
int med = (l+r)/2;
int x = a[med];
if(x>v) r = med;
else l = med;
}
// l - индекс искомого числа
Как показывает практика построение корневой декомпозиции на массиве и бинарный поиск сначала по блокам, а потом внутри блока ускоряет бинарный поиск в массиве (за счет более частого попадания в кэш). Несложно убедиться, что асимптотика остается прежней \( 2 * \log{ \sqrt{n} } = \log{n} \) .
Не обязательно искать по какому-то "материальному" объекту вроде элемента массива. Бывают задачи, для которых ответ легче найти с помошь бинарного поиска.
Буровая установка «Мегабур 2022» для прокладки туннелей метро Байтсбурга имеет \(n\) двигателей. Питание установки устроено таким образом, что на все двигатели подается одно и то же целочисленное напряжение \(x\). У каждого двигателя есть два режима, если на него подается напряжение \(x\), то \(i\)-й двигатель работает в первом режиме, если \(x\le z_i\) и во втором режиме, если \(x>z_i\). При этом \(i\)-й двигатель характеризуется удельной мощностью \(a_i\) в первом режиме и \(b_i\) во втором режиме. Это означает, что увеличение напряжения на \(1\) когда двигатель находится в первом режиме, приводит к увеличению его мощности на \(a_i\), а во втором режиме приводит к увеличению его мощности на \(b_i\). Иначе говоря, при подаче напряжения \(x\), если \(i\)-й двигатель находится в первом режиме он работает с мощностью \(a_ix\), а если во втором режиме, то с мощностью \(a_iz_i+b_i(x−z_i) \). Для прокладки туннеля суммарная мощность двигателей должна быть не меньше \(p\). Какое минимальное целочисленное напряжение необходимо подать на установку, чтобы суммарная мощность двигателей была больше или равна \(p\)?
Решать такую задачу можно с помошью бинарного поиска по ответу, а именно по искомому напряжению. На каждой итерации бинарного поиска будем рассчитывать мощность и сравнивать с \(p\).
Бинарный поиск работает только когда каждый элемент больше/меньше предыдущего (т.е. либо возрастает, либо убывает) Когда функция (последовательность) сначала возрастает, а потом убывает или убывает, а потом возрастает, следует использовать тернарный поиск. Парабола - пример такой функции. Пусть задача стоит в нахождении максимума в последовательности, которая сначала возрастает, а потом убывает. Границы \(l\) и \(r\) сохранятся, но теперь одной "пристрелочной" точки недостаточно, поэтому возьмем две - \( p_1 = \lfloor \frac{l+r}{3} \rfloor \) и \(p_2 = \lfloor \frac{2*(l+r)}{3}\rfloor \). Проще говоря - точку с первой трети и последней трети нашего промежутка.
Теперь рассмотрим эти две точки. Возможно два значимых случая: 1) \(f(p_1) < f(p_2) \), тогда присвоим \(l:= p_1\) 2) \(f(p_1) > f(p_2)\), в противном случае - \(r:= p_2\)
Остановится можно, когда интервал составит маленькое значение. Асимптотика - \(O(\log_{1.5}{n})\)
Важно! Тернарный поиск можно использовать только когда значения строго возрастают и строго убывают! Если два элемента подряд равны, то выполнить тернарный поиск не получится!
Почему? + интересная версия тернарникаНа самом деле, мы производим бинарный поиск по производной (к слову, многие так и делают - выбирают какое-то med и проверяют - меньше ли a[med] чем a[med+1]), так как производная сначала строго больше нуля, а потом строго меньше (в случае перевернутой параболы).
Но, если попадутся два равных элемента подряд, производная станет равна нулю! То есть она будет скакать то вверх, то вниз. И когда мы наткнемся на два равных элемента, непонятно что делать.