Алгоритмічні задачі на пошук

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]