Бинарный поиск на Python

Бинарный поиск - это алгоритм поиска элемента в упорядоченном списке или массиве данных. Он работает следующим образом:

1. Массив или список должен быть предварительно упорядочен по возрастанию или убыванию.

2. Алгоритм начинает поиск с середины списка или массива.

3. Он сравнивает значение искомого элемента с элементом в средней позиции. Если эти значения совпадают, поиск завершается.

4. Если значение искомого элемента меньше, чем значение элемента в середине, то искомый элемент может находиться только в первой половине массива. В этом случае алгоритм повторяется для первой половины списка, игнорируя вторую половину.

5. Если значение искомого элемента больше, чем значение элемента в середине, то искомый элемент может находиться только во второй половине массива. В этом случае алгоритм повторяется для второй половины списка, игнорируя первую половину.

6. Процесс продолжается, пока искомый элемент не будет найден или пока не будет оставаться только один элемент в списке, который будет проверяться на соответствие искомому.

Бинарный поиск отличается от простого линейного поиска тем, что он работает на упорядоченных данных и имеет более эффективную сложность времени выполнения. В то время как линейный поиск может выполняться за линейное время O(n), где n - количество элементов в списке, бинарный поиск обеспечивает логарифмическую сложность времени выполнения O(log n).

Реализуем бинарный поиск на Python

Функция binary_search получает отсортированный массив и значение. Если значение присутствует в массиве, то функция