Как работает алгоритм бинарного поиска?

Алгоритм бинарного поиска — это эффективный метод нахождения позиции целевого элемента в отсортированном массиве (или списке).

Принцип работы:

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