Приклади задач для лінійного і бінарного пошуку

3.1 Задача на знаходження елемента у масиві з використанням лінійного пошуку

Задача: Дано масив чисел. Потрібно знайти індекс заданого числа з використанням лінійного пошуку. Якщо число не знайдено, повернути -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
result = linear_search(arr, target)
print(f"Елемент {target} знайдено на індексі {result}")  # Виведення: Елемент 7 знайдено на індексі 2

# Приклад використання для елемента, якого немає у масиві:
target = 5
result = linear_search(arr, target)
print(f"Елемент {target} знайдено на індексі {result}")  # Виведення: Елемент 5 знайдено на індексі -1

Пояснення:

• Функція linear_search проходить по кожному елементу масиву arr і порівнює його з target.
• Якщо елемент знайдено, повертається його індекс.
• Якщо всі елементи перевірені і шукане значення не знайдено, функція повертає -1.

Покрокове виконання:

1. Масив [4, 2, 7, 1, 9, 3] і шукане значення 7.
2. Початок пошуку: порівнюється перший елемент (4) з 7 — не співпадає.
3. Перехід до наступного елемента (2) — не співпадає.
4. Перехід до наступного елемента (7) — співпадає.
5. Повернення індексу 2.

3.2 Задача на знаходження елемента у відсортованому масиві з використанням бінарного пошуку

Задача: Дано відсортований масив чисел. Потрібно знайти індекс заданого числа з використанням бінарного пошуку. Якщо число не знайдено, повернути -1.

Приклад:

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
result = binary_search(sorted_array, target)
print(f"Елемент {target} знайдено на індексі {result}")  # Виведення: Елемент 7 знайдено на індексі 3

# Приклад використання для елемента, якого немає у масиві:
target = 6
result = binary_search(sorted_array, target)
print(f"Елемент {target} знайдено на індексі {result}")  # Виведення: Елемент 6 знайдено на індексі -1

Пояснення:

• Функція binary_search використовує два вказівники (left і right), щоб відстежувати межі пошуку у масиві arr.
• На кожній ітерації знаходиться середній елемент масиву і порівнюється з target.
• Якщо середній елемент дорівнює target, повертається його індекс.
• Якщо target менше середнього елемента, пошук продовжується у лівій половині масиву.
• Якщо target більше середнього елемента, пошук продовжується у правій половині масиву.
• Якщо межі перетинаються і елемент не знайдено, повертається -1.

Покрокове виконання:

1. Відсортований масив [1, 3, 5, 7, 9, 11, 13] і шукане значення 7.
2. Початкові межі пошуку: left = 0, right = 6.
3. Знаходження середнього елемента: mid = (0 + 6) // 2 = 3.
4. Порівняння середнього елемента (7) з target (7) — співпадає.
5. Повернення індексу 3.

3.3 Порівняння і вибір підходящого алгоритму пошуку для різних задач

Порівняння лінійного і бінарного пошуку:

Вибір підходящого алгоритму

Лінійний пошук:

• Використовується, коли дані не відсортовані.
• Підходить для невеликих масивів або списків.
• Застосовується, коли кількість елементів невелика і час виконання не критичний.

Бінарний пошук:

• Застосовується, коли дані відсортовані.
• Ідеальний для великих масивів, де швидкість пошуку має значення.
• Ефективний, якщо потрібний частий пошук в одному і тому ж наборі даних (можна попередньо відсортувати дані).

3.4 Практичні завдання для закріплення матеріалу

Завдання 1: Лінійний пошук

Дано масив чисел. Напишіть функцію для пошуку заданого числа з використанням лінійного пошуку. Функція повинна повертати індекс знайденого елемента або -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
result = linear_search(arr, target)
print(f"Елемент {target} знайдено на індексі {result}")  # Виведення: Елемент 7 знайдено на індексі 2

# Додаткові тести:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Завдання 2: Бінарний пошук

Дано відсортований масив чисел. Напишіть функцію для пошуку заданого числа з використанням бінарного пошуку. Функція повинна повертати індекс знайденого елемента або -1, якщо елемент не знайдено.

Приклад:

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
result = binary_search(sorted_array, target)
print(f"Елемент {target} знайдено на індексі {result}")  # Виведення: Елемент 7 знайдено на індексі 3

# Додаткові тести:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Завдання 3: Порівняння лінійного і бінарного пошуку

Дано масив чисел. Напишіть дві функції для пошуку заданого числа: одну з використанням лінійного пошуку, іншу з використанням бінарного пошуку. Порівняйте продуктивність обох функцій на великих масивах.

Приклад:

import time
import random

# Лінійний пошук
def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

# Бінарний пошук
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

# Генерація великого масиву
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# Порівняння продуктивності
start_time = time.time()
linear_search(large_array, target)
print(f"Лінійний пошук зайняв: {time.time() - start_time:.6f} секунд")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Бінарний пошук зайняв: {time.time() - start_time:.6f} секунд")