Описание
Бинарный поиск - одна из самых полезных вещей в программировании, которая, несмотря на свою простоту, используется очень часто.
Определение
Бинарный поиск, далее бинпоиск, использует идею разделяй и властвуй для быстрого поиска конкретного элемента среди упорядоченного набора элементов. Идея очень проста, мы разделяем область поиска на 2 равных половины и смотрим, в какой из них наше число может находиться, там и продолжаем поиск. Получается, что если у нас будет n упорядоченных элементов, то весь поиск будет работать за , что намного быстрее чем поиск элемента вручную за n. Но поиск элемента в массиве, это маленький пример того, какие возможности несет за собой бинпоиск. Если взять эту идею глобально, то выходит, что бинпоиск умеет работать с непрерывными функциями таким образом: 1. Мы находим 2 точки, в которой значение меньше нужного и в которой значение больше нужного. 2. Мы пользуемся идеей непрерывности функции, что дает нам понимание того, что между значением больше нужного и значением меньше нужного обязательно лежит нужное. 3. Мы делим отрезок пополам и сужаем область поиска, пользуясь пунктом 2. И самым интересным заключается то, что нам необязательны значения большие или меньшие нужного, если мы можем доказать второй пункт таким образом: Между точкой A и точкой B всегда лежит искомая точка C, то нам не важны ни непрерывность функции, ни значения большие или меньшие C. К сожалению, редко все так складывается, что бинпоиск применим к задаче, но функция в ней не непрерывна и используется свойство, отличное от 2.
Бинпоиск по ответу
Из сказанного мной раньше вытекает логичное продолжение, если представить ответ на задачу, как функцию от какого-то входного параметра n, то можно будет сделать бинпоиск по этой функции таким образом: 1. Мы находим 2 значения, при которых ответ больше и меньше нужного 2. Мы делим отрезок входящих значений пополам и смотрим, как соотносятся искомый ответ и ответ в середине отрезка. 3. Продолжаем искать ответ на нужной половине отрезка Это также очень классная идея, которая имеет множество применений в задачах, но сталкивается с парой трудностей. В таких задачах иногда бывает сложно найти значения, большие и меньшие данного, ведь функции не всегда возрастающие или убывающие, а ещё иногда бывают смешанными, что подталкивает нас к использованию алгоритмов для поиска минимума и максимума функций, таких, как метод отжига или метод Ньютона.
Примечание
Можно придумать задачу, в которой вся сложность в придумывании умного бинпоиска, который не основан на свойстве 2, а на каких-то своих соображениях, которые также работают с идеей бинпоиска