Это старая версия документа.
Данный алгоритм является основным алгоритмом поиска.
Давай те рассмотрим данный алгоритм на примере задачи: ваш друг загадывает число из заданного заранее интервала [left, right], а вам требуется написать программу, которая будет отгадывать его (то есть ваш друг будет отвечать: «меньше», «больше» или «равно» на каждое предположение вашей программы). Заметим, что если заданный интервал достаточно большой, то обычный перебор всех возможных чисел будет работать очень долго (например если число может быть до 1018).
Давай те каждый раз брать середину интервала mid и если загаданное число меньше, то переходить к интервалу [l,mid], а иначе к [mid + 1, r]. Действительно, если элемент меньше mid, то и меньше всех элементов, которые находятся правее (то есть элементов больших чем mid). Так будем переходить от одного интервала к другому, пока left не совпадет с right, потому что в этот момент мы с уверенностью сможем сказать, что угадали число.
while (left < right) { int mid = (left + right) / 2; printf("%d", mid); scanf("%c", ans); if (ans == '=') { right = mid; break; } if (ans == '<') right = mid; else left = mid + 1; } printf("Загаданное число = %d", right);
Действовать будем абсолютно аналогично, только теперь left, right и mid - это индексы заданного массива.
Пусть нам нужно найти номер элемента равного key или вывести -1, если его нет в массиве:
while (left < right){ int mid = (left + right ) / 2; if (a[mid] <= k) left = mid + 1; else right = mid; } if (a[right] == k) printf("%d", right); else printf("-1");
Так же как и для массива мы можем исключать половину интервала возможных значении на каждом шаге. Если функция не монотонна, то скорее всего найдутся не все ответы.
Приведем пример для решения задачи о нахождении корня из N (>= 1) с точностью до 6 знаков:
right = N; left = 1; eps = 1e-7; while (fabs(left - right) > eps) { double mid = (left + right) / 2; if (mid * mid <= x) left = mid; else right = mid; }
Пусть нам дана какая то задача, где нужно максимизировать (минимизировать) ответ, но операция получения ответа достаточно трудоемка и мы не можем просто перебрать все возможные варианты.
Воспользуемся бинарным поиском, за left примем минимально возможный ответ по условиям задачи, а за right - максимально возможный. Теперь будем пробовать получить ответ равный mid = (left + right) / 2, если нам это удается, то left = mid, иначе right = mid.
Задачи, в которых можно использовать данный алгоритм:
http://informatics.mccme.ru/moodle/mod/statements/view.php?id=192
http://informatics.mccme.ru/moodle/mod/statements/view.php?id=1966
http://informatics.mccme.ru/moodle/mod/statements/view.php?id=3516