Алгоритм бинарного (двоичного) поиска имеет логарифмическую временную сложность O(log n).
Принцип работы бинарного поиска:
- Требует отсортированного массива (или списка).
- На каждом шаге сравнивает искомый элемент с элементом в середине текущего диапазона поиска.
- Если элемент совпадает, поиск завершен.
- Если искомый элемент меньше среднего, поиск продолжается в левой половине диапазона.
- Если искомый элемент больше среднего, поиск продолжается в правой половине диапазона.
- Диапазон поиска сокращается вдвое на каждом шаге.
Пример реализации на Python:
python
Логарифмическая сложность обусловлена тем, что количество операций пропорционально логарифму от размера входных данных (n), так как на каждом шаге пространство поиска уменьшается в два раза.