Бинарный поиск работает, анализируя отсортированный массив, последовательно деля пополам интервал поиска.
- Инициализация: Определяется левая и правая граница интервала поиска (обычно начало и конец массива).
- Сравнение: Вычисляется индекс середины интервала. Значение по этому индексу сравнивается с искомым элементом.
- Уменьшение интервала:
- Если значение в середине совпадает с искомым, элемент найден.
- Если значение в середине больше искомого, поиск продолжается в левой половине интервала. Правая граница сдвигается к середине-1.
- Если значение в середине меньше искомого, поиск продолжается в правой половине интервала. Левая граница сдвигается к середине+1.
- Повторение: Шаги 2 и 3 повторяются до тех пор, пока элемент не будет найден или интервал поиска не станет пустым.
Сложность алгоритма O(log n), что значительно эффективнее линейного поиска для больших массивов.
Пример реализации на Python:
python