Алгоритм бинарного поиска — это эффективный метод нахождения позиции целевого элемента в отсортированном массиве (или списке).
Принцип работы:
- Начало поиска: Определение границ интервала поиска - начало (left) и конец (right) массива.
- Вычисление середины: На каждой итерации определяется средний индекс (middle) текущего интервала:
middle = (left + right) / 2.
- Сравнение: Целевой элемент сравнивается с элементом по индексу
middle.
- Если целевой элемент равен элементу по индексу
middle, поиск завершен, элемент найден.
- Если целевой элемент меньше элемента по индексу
middle, поиск сужается до левой половины интервала: right = middle - 1.
- Если целевой элемент больше элемента по индексу
middle, поиск сужается до правой половины интервала: left = middle + 1.
- Повторение: Шаги 2 и 3 повторяются до тех пор, пока целевой элемент не будет найден или пока интервал поиска не станет пустым (
left > right).
- Результат: Если элемент найден, возвращается его индекс. Если нет, возвращается индикатор отсутствия (например, -1).
Преимущества:
- Высокая скорость (логарифмическая сложность O(log n)), особенно для больших наборов данных.
Недостатки:
- Требует предварительной сортировки массива.
- Применим только к коллекциям с произвольным доступом по индексу.
Пример реализации на Python:
python