Поиск данных в Python: методы и примеры

Раздел: Алгоритмы -> алгоритмы поиска

Основы алгоритмов поиска

Как найти элемент в отсортированном массиве быстрее, чем за линейное время?

Бинарный поиск (binary search) позволяет найти элемент за O(log n) при условии предварительной сортировки. Основная идея - разделение области поиска на две равные части и сравнение с центральным элементом.


def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Python алгоритм поиска (алгоритм поиска в python)

Пример использования:


arr = [1, 3, 5, 7, 9, 11]
index = binary_search(arr, 7)
print(index)

Рекурсивная версия:


def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid+1, right)
    else:
        return binary_search_recursive(arr, target, left, mid-1)

Типичные проблемы:

Отсутствие сортировки - бинарный поиск не даст правильный результат.
Ошибка в вычислении середины: использование (left+right)//2 для больших массивов без риска переполнения в Python не критично, но важно для других языков.
Бесконечный цикл при неправильном обновлении границ (например, left = mid вместо left = mid+1).

Как выполнить линейный поиск в неотсортированном списке?

Линейный поиск - перебор всех элементов до нахождения нужного. Простейший алгоритм, работает за O(n). Применяется когда данные не отсортированы или малого размера.


def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1


arr = [4, 2, 7, 1, 9]
print(linear_search(arr, 7))

Недостаток: при больших объёмах данных производительность низкая. Альтернатива - использование встроенных методов.

Какие встроенные средства Python ускоряют поиск?

Python предоставляет list.index(), оператор in и модуль bisect для отсортированных последовательностей.

list.index() - линейный поиск с возвратом индекса первого вхождения. Вызывает исключение ValueError, если элемент не найден.


arr = [10, 20, 30, 40]
try:
    idx = arr.index(30)
    print(idx)
except ValueError:
    print("Не найдено")

bisect - бинарный поиск в отсортированном списке. Функция bisect_left возвращает позицию для вставки элемента.


import bisect
arr = [1, 3, 5, 7]
pos = bisect.bisect_left(arr, 5)
if pos < len(arr) and arr[pos] == 5:
    print("Найден на", pos)
else:
    print("Нет")

Найден на 2

Важно: bisect требует отсортированного списка; list.index() работает за O(n); оператор in для списка также O(n), но для множества set - O(1).

Как организовать поиск в динамической структуре, например, в бинарном дереве?

Бинарное дерево поиска (BST) позволяет выполнять операции вставки, удаления и поиска за O(log n) в среднем. Каждый узел имеет ключ, левое поддерево с меньшими ключами, правое - с большими.


class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def bst_search(root, target):
    if root is None or root.key == target:
        return root
    if target < root.key:
        return bst_search(root.left, target)
    else:
        return bst_search(root.right, target)


root = Node(10)
root.left = Node(5)
root.right = Node(15)
result = bst_search(root, 15)
print(result.key if result else None)

Недостаток: при несбалансированном дереве (например, вставка упорядоченных ключей) вырождается в связанный список, сложность возрастает до O(n). Решение - использование самобалансирующихся деревьев (AVL, красно-чёрных).

Как обеспечить мгновенный доступ к элементу по ключу?

Хэш-таблицы (словари dict и множества set) обеспечивают поиск за O(1) в среднем. Ключ хэшируется, и значение сохраняется в соответствующей корзине.


d = {"apple": 1, "banana": 2, "cherry": 3}
if "banana" in d:
    print(d["banana"])

Для поиска по значению без индексации придётся перебирать, так как dict оптимизирован для поиска по ключу.

Проблемы: необходимость хэшируемости ключей (неизменяемые типы); коллизии могут замедлить поиск; большой расход памяти. Для примитивных ключей (int, str) хэш-таблицы работают отлично.

Как найти вхождение подстроки в строку?

Наивный алгоритм поиска подстроки сравнивает подстроку с каждым возможным сдвигом. Сложность O(n*m). Для больших текстов лучше использовать более эффективные алгоритмы (Кнут-Моррис-Пратт, Бойер-Мур).


def naive_search(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            return i
    return -1


text = "Hello, world!"
print(naive_search(text, "world"))

Основная проблема - низкая скорость на длинных строках с повторяющимися символами. Альтернатива - встроенный метод str.find(), который реализован на C и работает быстрее.

Расширенные примеры поисковых алгоритмов

Пример 1: Бинарный поиск с нахождением левой и правой границы дубликатов.

Пример


def binary_search_left(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left+right)//2
        if arr[mid] < target:
            left = mid+1
        else:
            right = mid-1
    return left

def binary_search_right(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left+right)//2
        if arr[mid] <= target:
            left = mid+1
        else:
            right = mid-1
    return right

arr = [1, 2, 2, 2, 3, 4]
l = binary_search_left(arr, 2)
r = binary_search_right(arr, 2)
print(f"Первое вхождение: {l}, последнее: {r}")

Первое вхождение: 1, последнее: 3

Пример 2: Поиск элемента в бинарном дереве поиска без рекурсии (итеративный).

Пример


class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def bst_search_iter(root, target):
    current = root
    while current:
        if current.key == target:
            return current
        elif target < current.key:
            current = current.left
        else:
            current = current.right
    return None

root = Node(20)
root.left = Node(10)
root.right = Node(30)
root.left.left = Node(5)
root.right.right = Node(40)
node = bst_search_iter(root, 30)
print(node.key if node else "None")

Пример 3: Поиск элемента по предикату с помощью filter и next.

Пример


data = [{'name': 'Alice', 'age': 30}, {'name': 'Bob', 'age': 25}, {'name': 'Charlie', 'age': 35}]
found = next(filter(lambda x: x['age'] > 30, data), None)
print(found)

{'name': 'Charlie', 'age': 35}

Пример 4: Поиск подстроки с использованием алгоритма Кнута-Морриса-Пратта (простая реализация).

Пример


def kmp_search(text, pattern):
    n, m = len(text), len(pattern)
    if m == 0:
        return 0
    lps = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = lps[j-1]
        if pattern[i] == pattern[j]:
            j += 1
        lps[i] = j
    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = lps[j-1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            return i - m + 1
    return -1

text = "ABC ABCDAB ABCDABCDABDE"
pattern = "ABCDABD"
print(kmp_search(text, pattern))

алгоритм поиска в Python - comments

Python алгоритм поиска (python)