Алгоритми пошуку

Лінійний та бінарний пошук у даних: ідея, код, та коли який алгоритм обирати.

1 Що таке пошук?

Пошук — це задача знайти елемент у наборі даних або визначити, що його там немає. У програмуванні пошук зустрічається всюди: знайти товар у кошику, користувача за ID, слово у тексті, потрібний рівень у списку балів.

Ключова думка

Вибір алгоритму залежить від структури даних і того, чи відсортовані вони.

2 Лінійний пошук (Linear Search)

Лінійний пошук перевіряє елементи по черзі: перший, другий, третій… поки не знайде потрібний або не закінчаться дані. Він працює з будь-якими списками — навіть якщо вони не відсортовані.

linear_search.py 
def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

nums = [7, 1, 9, 3]
print(linear_search(nums, 9))  # 2
print(linear_search(nums, 5))  # -1
Складність: у найгіршому випадку треба перевірити всі елементи → O(n).

3 Бінарний пошук (Binary Search)

Бінарний пошук працює лише тоді, коли дані відсортовані. Ідея проста: ми кожного разу ділимо відрізок навпіл і відкидаємо половину, яка точно не підходить.

Важливо

Якщо список не відсортований — бінарний пошук може повернути неправильний результат.

binary_search.py 
def binary_search(items, target):
    left = 0
    right = len(items) - 1

    while left <= right:
        mid = (left + right) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

sorted_nums = [1, 3, 7, 9, 12, 20]
print(binary_search(sorted_nums, 9))  # 3
Складність: кожен крок “викидає” половину → O(log n).

4 Пошук у Python “по-дорослому”

Часто вам не потрібно писати пошук вручну:

Оператор in

Перевіряє, чи є елемент у списку. 

nums = [1, 3, 7]
print(3 in nums)   # True
print(9 in nums)   # False

Метод index()

Повертає індекс (але якщо елемента нема — буде помилка). 

nums = [1, 3, 7]
print(nums.index(7))  # 2

Висновок

Лінійний пошук — універсальний, але повільніший. Бінарний — дуже швидкий, але потребує відсортованих даних. У реальних задачах швидкість часто залежить від того, як ви зберігаєте і готуєте дані.

linear binary sorted O(n) O(log n)