бинарный поиск

EN: binary search

Алгоритм поиска, работающий с отсортированным массивом: многократно сравнивает цель с серединным элементом и отбрасывает половину, в которой цели нет. Каждый шаг вдвое уменьшает оставшееся пространство поиска, что даёт O(log n) времени и O(1) дополнительной памяти.