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

1.1 Визначення лінійного пошуку

Лінійний пошук (також відомий як послідовний пошук) — це алгоритм пошуку елемента в списку або масиві, який послідовно перевіряє кожен елемент до тих пір, поки не знайде збіг або не перевірить всі елементи. Це найпростіший алгоритм пошуку, який не потребує попереднього сортування даних.

Основні принципи:

• Послідовна перевірка: Алгоритм проходить по кожному елементу масиву або списку, порівнюючи його з шуканим значенням.
• Припинення пошуку: Пошук припиняється, коли знайдений елемент, що відповідає шуканому значенню, або коли всі елементи перевірені.
• Не потребує сортування: Лінійний пошук може застосовуватися до невідсортованих даних.
• Застосування: Лінійний пошук може застосовуватися до будь-яких структур даних, які підтримують ітерацію, включаючи списки і масиви.

Лінійний пошук має часову складність O(n), де n — це кількість елементів в масиві або списку. У найгіршому випадку алгоритму потрібно буде перевірити всі n елементів, щоб знайти шукане значення або визначити його відсутність.

Аналіз часової складності:

• Найкращий випадок (Best case): Елемент знайдений на першому місці, O(1).
• Середній випадок (Average case): Елемент знайдений десь у середині, O(n/2), що еквівалентно O(n).
• Найгірший випадок (Worst case): Елемент знайдений на останньому місці або відсутній, O(n).

1.2 Пошагова реалізація лінійного пошуку

Кроки лінійного пошуку:

• Ініціалізація: Встановити початковий індекс для пошуку (зазвичай нульовий індекс).
• Послідовна перевірка: Перевіряти кожен елемент списку або масиву на відповідність шуканому значенню.
• Умова завершення: Якщо елемент знайдений, повернути його індекс. Якщо всі елементи перевірені і шукане значення не знайдено, повернути спеціальне значення (зазвичай -1 або None).

Реалізація лінійного пошуку в Python:

def linear_search(arr, target):
    # Проходимо по кожному елементу масиву
    for index, element in enumerate(arr):
        # Якщо поточний елемент дорівнює шуканому значенню, повертаємо його індекс
        if element == target:
            return index
    # Якщо елемент не знайдено, повертаємо -1
    return -1

Пошагове пояснення реалізації:

• Ініціалізація циклу: Використовується цикл for з функцією enumerate, яка повертає індекс і елемент масиву на кожній ітерації.
• Порівняння: На кожній ітерації поточний елемент порівнюється з шуканим значенням (target).
• Повернення індексу: Якщо поточний елемент дорівнює шуканому значенню, повертається індекс цього елемента.
• Повернення -1: Якщо цикл завершився і шуканий елемент не був знайдений, повертається -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

1.3 Приклади задач, що вирішуються за допомогою лінійного пошуку

Лінійний пошук використовується для вирішення багатьох задач, пов'язаних з пошуком елементів у колекціях даних. Ось кілька прикладів таких задач:

Задача 1: Пошук елемента в масиві

Потрібно знайти задане число в масиві чисел.

Приклад:

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

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"Елемент {target} знайдений на індексі {index}")  # Вивід: Елемент 70 знайдений на індексі 3

Задача 2: Перевірка наявності елемента в списку

Потрібно перевірити, чи присутнє задане значення в списку рядків.

Приклад:

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"Елемент {target} {'знайдений' if found else 'не знайдений'}")  # Вивід: Елемент cherry знайдений

Задача 3: Пошук мінімального або максимального елемента

Потрібно знайти мінімальне або максимальне значення у списку.

Приклад:

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"Мінімальне значення: {min_value}")  # Вивід: Мінімальне значення: 2

Задача 4: Пошук першого входження

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

Приклад:

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

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"Перше входження {target} на індексі {index}")  # Вивід: Перше входження 2 на індексі 1

Задача 5: Підрахунок кількості входжень

Підрахувати кількість входжень заданого елемента у списку.

Приклад:

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"Елемент {target} зустрічається {count} рази")  # Вивід: Елемент 2 зустрічається 3 рази