Изучаем структуры данных и алгоритмы в Python

Поиск первого и последнего вхождения элемента в отсортированном массиве

Для дублирующихся элементов нужно найти границы. Используем два бинарных поиска.

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

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

arr = [1, 2, 2, 2, 3, 4, 5]
print(f"Первое вхождение 2: {find_first(arr, 2)}")
print(f"Последнее вхождение 2: {find_last(arr, 2)}")

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

Бинарный поиск в повёрнутом массиве

Дан отсортированный массив, который был циклически сдвинут. Необходимо найти элемент.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:
            # левая часть отсортирована
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # правая часть отсортирована
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

rotated = [4, 5, 6, 7, 0, 1, 2]
print(f"Индекс 0: {search_rotated(rotated, 0)}")
print(f"Индекс 3: {search_rotated(rotated, 3)}")

Индекс 0: 4
Индекс 3: -1

Сортировка слиянием (merge sort) с подробным разбором

Алгоритм делит массив пополам, рекурсивно сортирует половины и сливает их.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr)

[3, 9, 10, 27, 38, 43, 82]

Проблема: Требуется дополнительная память O(n). Для больших массивов может быть критично. Альтернатива – сортировка на месте (heap sort).

Быстрое возведение в степень (бинарное возведение)

Алгоритм вычисляет a^n за O(log n) путём разложения степени по двоичному представлению.

def fast_pow(a, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        half = fast_pow(a, n // 2)
        return half * half
    else:
        return a * fast_pow(a, n - 1)

print(fast_pow(2, 10))
print(fast_pow(3, 5))

1024
243

Поиск подстроки алгоритмом Кнута-Морриса-Пратта (KMP)

КМП ищет вхождения строки pattern в текст за O(n+m) без возврата.

def kmp_search(text, pattern):
    # построение префикс-функции
    n, m = len(text), len(pattern)
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    # поиск
    i = j = 0
    indices = []
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            indices.append(i - j)
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return indices

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp_search(text, pattern))

[10]