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

Введение

Бинарный поиск — это эффективный алгоритм поиска элемента в отсортированном массиве. Он работает путем деления массива пополам и сравнения искомого элемента с элементом в середине массива. В зависимости от результата сравнения, поиск продолжается в левой или правой половине массива. В данной статье реализуем бинарный поиск в 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. Надеюсь Вам понравилась статья, желаю удачи и успехов! 🙂