Очередной шаг в изучении алгоритмов не мыслим без алгоритмов поиска.
И так, перед нами может стоять задача "найти элемент в массиве данных", или "найти положение элемента".
Простейшее решение - это пройтись по всему массиву пока мы не обнаружим искомый элемент, а в случае его отсутствия "скажем" что такового не имеется.
Такой алгоритм называется Линейным поиском, потому что в худшем случае (когда элемент находится в конце списка размера N) мы совершим N операций сравнения, т.е. время работы алгоритма линейно зависит от размера входного массива - О(n).
Алгоритм Бинарного поиска позволит выполнить операцию поиска быстрее, но только при условии что входной массив отсортирован.
Описание:
Двоичный (он же бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве. Идея алгоритма заключается в делении массива пополам и дальнейшем "отбрасывании" не нужной части. Т.о. на каждом шаге алгоритма мы уменьшаем область поиска вдвое.
Мы искали место, в котором находится искомый элемент, тогда зачем нам Left и Right? Если внимательно посмотреть на возвращаемые значения будет видно что Left = X (если X найден) или Left < X (если Х не найден), а Right всегда больше X. Таким образом мы нашли не просто место, а верхнюю границу для искомого элемента, где:
- · Left – индекс последнего вхождения искомого элемента в массив.
- · Right - индекс минимального элемента строго большего Х, а значит на его место можно вставить элемент Х (сдвинув все элементы после на один вправо) не нарушая порядка в массиве.
Изменив условие в п.5 «Если M[middle] > X» на «Если M[middle] >= X» мы найдем нижнюю границу искомого элемента, где Left < X, а Right ≥ X.
Блок-схема:
Код на Python 3.7:
Если требуется индекс места при условии что элемент найден, то просто добавляем вместо return [left, right] проверочное условие:
Алгоритмическая сложность:
Исходные данные: массив М длины N = 100.
Линейный поиск совершает 100 операций для поиска элемента в конце массива. Сколько операций совершит бинарный поиск?
Очень похоже на работу алгоритма сортировки слиянием, когда мы делили массив на половины. Количество операций будет считаться так же от логарифма: log₂(100) = 6.67.
Итого: Совершаем log(n) операций сужения границ ---> O(log(n)).
И на десерт: немного о прикладном применении.
Бинарный поиск может помочь легко решать уравнения. Мне этот метод помогал находить границы устойчивости системы при изучении ТАУ. Но для примера решим задачку попроще:
Найдем при каком значении X уравнение будет равно 0 ( или какому-либо другому значению)