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