Эффективные алгоритмы поиска в массивах: бинарный поиск и не только

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

Представьте: вы ищете контакт в телефоне с 10 000 записей. Линейный перебор может занять секунды, а бинарный поиск — миллисекунды. Понимание алгоритмов поиска — ключ к написанию быстрого и эффективного кода. В этой статье мы разберем основные алгоритмы поиска в массивах, от простого до сложного, с примерами на Python.

Линейный поиск: простота за счёт скорости

Самый очевидный способ — пройти по массиву от начала до конца. Сложность O(n). Подходит для небольших или неотсортированных массивов.

def linear_search(arr, target):
    """Линейный поиск: возвращает индекс target или -1"""
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Пример использования
arr = [3, 5, 1, 9, 2]
print(linear_search(arr, 9))  # Вывод: 3

Бинарный поиск: скорость на отсортированных данных

Если массив отсортирован, бинарный поиск сокращает время до 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

# Пример
arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 7))  # Вывод: 3

Варианты бинарного поиска

• Поиск левой границы: первое вхождение элемента (если есть дубликаты).
• Поиск правой границы: последнее вхождение.
• Поиск вставки: индекс, куда можно вставить элемент, сохраняя порядок.

def left_bound(arr, target):
    """Левая граница: первое вхождение или место вставки"""
    left, right = 0, len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

arr = [1, 2, 2, 3, 4]
print(left_bound(arr, 2))  # Вывод: 1 (первый индекс с двойкой)

Тернарный поиск: для унимодальных функций

Когда массив сначала возрастает, потом убывает (или наоборот), тернарный поиск находит экстремум за O(log n).

def ternary_search(arr, left, right):
    """Поиск максимума в унимодальном массиве"""
    while right - left > 3:
        m1 = left + (right - left) // 3
        m2 = right - (right - left) // 3
        if arr[m1] < arr[m2]:
            left = m1
        else:
            right = m2
    # Линейный поиск на оставшемся отрезке
    max_val = arr[left]
    for i in range(left, right + 1):
        if arr[i] > max_val:
            max_val = arr[i]
    return max_val

arr = [1, 3, 7, 5, 2]
print(ternary_search(arr, 0, len(arr)-1))  # Вывод: 7

Поиск с помощью хеш-таблиц: O(1) в среднем

Если нужен многократный поиск, лучше использовать хеш-таблицу. Преобразуем массив в словарь (ключ — значение, значение — индекс).

def hash_search(arr, target):
    """Поиск через хеш-таблицу: O(1) в среднем"""
    hash_map = {val: i for i, val in enumerate(arr)}
    return hash_map.get(target, -1)

arr = [3, 5, 1, 9, 2]
print(hash_search(arr, 9))  # Вывод: 3

Недостаток: требуется дополнительная память O(n).

Экспоненциальный поиск: комбинация для больших массивов

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

def exponential_search(arr, target):
    """Экспоненциальный поиск: O(log i) где i — индекс элемента"""
    if arr[0] == target:
        return 0
    i = 1
    while i < len(arr) and arr[i] <= target:
        i *= 2
    # Бинарный поиск на отрезке [i//2, min(i, len(arr)-1)]
    left, right = i // 2, min(i, 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

arr = [1, 3, 5, 7, 9, 11, 13]
print(exponential_search(arr, 9))  # Вывод: 4

Интерполяционный поиск: для равномерно распределенных данных

Улучшение бинарного поиска: вместо середины использует формулу, основанную на значениях. Сложность O(log log n) в среднем, но O(n) в худшем.

def interpolation_search(arr, target):
    """Интерполяционный поиск: подходит для равномерного распределения"""
    left, right = 0, len(arr) - 1
    while left <= right and arr[left] <= target <= arr[right]:
        if left == right:
            if arr[left] == target:
                return left
            return -1
        # Формула интерполяции
        pos = left + ((target - arr[left]) * (right - left)) // (arr[right] - arr[left])
        if arr[pos] == target:
            return pos
        if arr[pos] < target:
            left = pos + 1
        else:
            right = pos - 1
    return -1

arr = [10, 20, 30, 40, 50]
print(interpolation_search(arr, 30))  # Вывод: 2

Практический вывод: что делать прямо сейчас

Выберите подходящий алгоритм в зависимости от данных:

• Если массив небольшой или не отсортирован — используйте линейный поиск.
• Если массив отсортирован — бинарный поиск.
• Если нужен многократный поиск — хеш-таблица.
• Если массив очень большой и отсортирован — экспоненциальный поиск.
• Если данные равномерно распределены — интерполяционный поиск.

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