Алгоритм двоичного поиска Python

Поиск в отсортированных списках осуществляется за логарифмическое время O(log n). Запускайте и разбирайтесь в двоичном поиске в Python, включая пошаговую логику, крайние случаи и оптимизации.

Попробуйте в редакторе

Обзор

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

Поиск начинается с проверки среднего элемента массива. Если целевое значение соответствует среднему элементу, возвращается его позиция. Если цель меньше, алгоритм сужает поиск до нижней половины; если цель больше, она сужает ее до верхней половины. Этот процесс повторяется до тех пор, пока элемент не будет найден или пока размер подмассива не упадет до нуля.

Чтобы реализовать бинарный поиск в Python, мы используем два указателя (нижний и верхний) для отслеживания активных границ поиска. Поскольку пространство поиска уменьшается вдвое на каждом шаге, алгоритм выполняется за время O(log n), что делает его идеальным для больших баз данных.

Код и вывод выполнения

Стандартная реализация итеративного двоичного поиска, которая возвращает индекс целевого элемента в отсортированном списке.

binary_search.py

Попробуйте в редакторе

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = arr[mid]
        
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
            
    return -1

# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23

index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
    print(f"Target found at index: {index}")
else:
    print("Target not found in dataset")

Терминальный выход

Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5

Пошаговая реализация

Индексирование запросов и поиск в таблицах базы данных
Поиск пороговых или граничных значений в непрерывных математических диапазонах
Функции автозаполнения и поиска в текстовых полях

Часто задаваемые вопросы

Должен ли список быть отсортирован для работы бинарного поиска?

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

Зачем использовать итеративный двоичный поиск вместо рекурсивного двоичного поиска?

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

Связанные темы

Алгоритмы сортировки Python

Изучите алгоритмы сортировки Python. Визуализируйте пузырьковую сортировку и сортировку слиянием в контексте IDE браузера.

Учебное пособие по алгоритму сортировки слиянием Python

Узнайте, как реализовать сортировку слиянием в Python. Интерактивный пошаговый пример стратегии сортировки «Разделяй и властвуй».

Руководство по алгоритму быстрой сортировки Python

Изучите алгоритм быстрой сортировки в Python. Изучите выбор опорной точки, секционирование и рекурсию в этом интерактивном примере кодирования.