Введение
Бинарный поиск — это эффективный алгоритм поиска элемента в отсортированном массиве. Он работает путем деления массива пополам и сравнения искомого элемента с элементом в середине массива. В зависимости от результата сравнения, поиск продолжается в левой или правой половине массива. В данной статье реализуем бинарный поиск в Python.
Бинарный поиск в Python
Определим функцию с названием binary_search(), которая принимает отсортированный список arr и целевой элемент target. Внутри неё сначала создадим переменные low и high для определения границ поиска. low равна нулю (первому индексу списка), а high — индексу последнего элемента списка.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
Далее будет идти цикл while, который будет работать до тех пор, пока low не станет больше high. Внутри цикла вычислим средний индекс mid и сравниваем элемент в середине списка с целевым элементом (target).
Если элемент найден, то будет возвращена его позиция (индекс) в списке. Если элемент меньше целевого, то значение в low будет обновляться, чтобы исключить левую половину списка из поиска. Если элемент больше целевого, то значение будет обновляться уже в high, чтобы исключить правую половину списка из поиска.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
В случае отсутствия в списке искомого элемента функция вернёт -1:
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
Проверим работоспособность нашего поиска, создадим список и вызовем функцию binary_search() передав в качестве параметров список и число. Далее в условии проверим, если функция вернула -1, то элемент не был найден, иначе — был:
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
numbers = [1, 2, 3, 4, 5]
target = 4
result = binary_search(numbers, target)
if result == -1:
print("Элемент не найден")
else:
print(f"Элемент располагается по индексу {result}")
# Вывод: Элемент располагается по индексу 3
Заключение
В ходе статьи мы с Вами реализовали бинарный поиск в Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂
Мой Telegram канал
Мой YouTube канал
Курс по созданию телеграм-ботов на Python с фреймворком Aiogram