Алгоритмические задачи на поиск

9.1 Примеры задач, решаемых с помощью линейного и бинарного поиска

Линейный поиск

Задача на поиск элемента в массиве: Дан массив чисел и целевое значение. Необходимо найти индекс целевого значения в массиве.

Решение: Используем линейный поиск для проверки каждого элемента массива.

Пример реализации:

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

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

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

Задача на поиск элемента в отсортированном массиве: Дан отсортированный массив чисел и целевое значение. Необходимо найти индекс целевого значения в массиве.

Решение: Используем бинарный поиск для деления массива на половины и поиска целевого значения.

Пример реализации:

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

# Пример использования:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # Вывод: 3

9.2 Задачи на использование хеш-таблиц для оптимизации поиска

1. Поиск дубликатов в массиве

Задача: Дан массив чисел. Необходимо найти и вернуть все дубликаты в массиве.

Решение: Используем хеш-таблицу для отслеживания чисел, которые уже встречались. Если число встречается повторно, добавляем его в список дубликатов.

Пример реализации:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

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

2. Нахождение пар с заданной суммой

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

Решение: Используем хеш-таблицу для хранения чисел и проверки, образуют ли они пару с текущим числом, которая даёт целевую сумму.

Пример реализации:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# Пример использования
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Вывод: [(1, 5), (7, -1), (1, 5)]

9.3 Комбинированное использование различных методов поиска

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

Пример 1: Поиск элемента в массиве и проверка его существования в другом массиве

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

Решение:

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

Пример реализации:

def find_common_elements(arr1, arr2):
    hash_table = set(arr2)  # Хеш-таблица для второго массива
    common_elements = []

    for element in arr1:
        if element in hash_table:
            common_elements.append(element)

    return common_elements

# Пример использования:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # Вывод: [3, 4, 5]

Пример 2: Проверка, является ли подмассив массивом анаграмм с использованием хеш-таблицы

Дан массив строк и строка-шаблон. Необходимо проверить, является ли какая-либо подстрока массива строк анаграммой шаблона.

Решение:

• Используем хеш-таблицу для подсчёта частоты символов в шаблоне.
• Проходим по массиву строк и используем «скользящее окно» для проверки каждой подстроки на соответствие частотам символов.

Пример реализации:

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

def find_anagram_substring(arr, pattern):
    pattern_length = len(pattern)
    pattern_count = Counter(pattern)
    
    for i in range(len(arr) - pattern_length + 1):
        substring = arr[i:i + pattern_length]
        if is_anagram(substring, pattern):
            return True
    return False

# Пример использования:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # Вывод: True

9.4 Практические задания для закрепления материала

Задание 1: Поиск элемента в неотсортированном массиве

Дан массив чисел и целевое значение. Необходимо найти индекс целевого значения в массиве. Используйте линейный поиск.

Пример:

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

# Пример использования:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # Вывод: 2

Задание 2: Поиск дубликатов в массиве

Дан массив чисел. Найдите и верните все дубликаты в массиве с использованием хеш-таблицы.

Пример:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

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

2

Задача

Модуль 1: Python Core, 16 уровень, 8 лекция

Недоступна

Сумма чисел

Сумма чисел

Открыть

2

Задача

Модуль 1: Python Core, 16 уровень, 8 лекция

Недоступна

Общий подмассив

Общий подмассив

Открыть