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

4.1 Порівняння часової складності лінійного і бінарного пошуку

Давайте порівняємо часову складність лінійного і бінарного пошуку.

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

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

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

• Часова складність: O(log n), де n — кількість елементів у масиві або списку.
• Найкращий випадок: O(1) — елемент знайдений на першому кроці (середній елемент).
• Середній випадок: O(log n) — пошук у відсортованому масиві.
• Найгірший випадок: O(log n) — елемент знайдений на останньому кроці або відсутній.

Приклад аналізу часової складності

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

• Масив [1, 3, 5, 7, 9, 11, 13], шуканий елемент 7.
• Перевірка кожного елемента до знаходження 7 на індексі 3.
• Потрібно було 4 перевірки, що відповідає O(n).

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

• Масив [1, 3, 5, 7, 9, 11, 13], шуканий елемент 7.
• Середній елемент (7) знайдений на першому кроці.
• Потрібно було 1 перевірка, що відповідає O(log n).

4.2 Переваги та недоліки кожного методу

Розглянемо переваги та недоліки кожного типу пошуку.

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

Переваги:

• Простота реалізації: Лінійний пошук дуже легко реалізувати і зрозуміти.
• Немає вимог до даних: Лінійний пошук може застосовуватися до невідсортованих даних.
• Підходить для невеликих масивів: Лінійний пошук ефективний для масивів малого розміру.

Недоліки:

• Низька ефективність для великих масивів: Часова складність O(n) робить його неефективним для великих масивів.
• Тривалий час виконання: Для великих масивів лінійний пошук може зайняти багато часу, особливо якщо шуканий елемент знаходиться ближче до кінця масиву або відсутній.

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

Переваги:

• Висока ефективність для великих масивів: Часова складність O(log n) робить його дуже ефективним для великих масивів.
• Швидке виконання: Бінарний пошук значно швидший лінійного пошуку при роботі з великими відсортованими масивами.

Недоліки:

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

4.3 Коли використовувати який пошук

Розглянемо, коли використовувати лінійний пошук, а коли бінарний пошук.

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

Використовуйте лінійний пошук, коли:

• Масив або список не відсортовані.
• Розмір масиву або списку невеликий.
• Потрібна простота і швидке рішення без додаткових витрат на сортування.
• Потрібно знайти перше входження або всі входження елемента.
• Дані надходять у реальному часі, і їх попереднє сортування неможливе або недоцільне.

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

Використовуйте бінарний пошук, якщо:

• Масив або список відсортовані.
• Розмір масиву або списку великий.
• Частий пошук елементів в одному і тому ж наборі даних (можна попередньо відсортувати дані один раз).
• Важлива висока швидкість пошуку.
• Допустимо витратити час на попереднє сортування даних.

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

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

2. Пошук першого входження в масиві

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

Приклад:

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

words = ["apple", "banana", "cherry", "date", "banana"]
target = "banana"
print(linear_search(words, target))  # Вивід: 1

3. Пошук у даних реального часу

Знайти елемент у потоці даних, що надходять в реальному часі.

Приклад:

import random

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

stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))

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

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
print(binary_search(sorted_array, target))  # Вивід: 3

2. Частий пошук у великому наборі даних

Часто шукати елементи в великому відсортованому масиві чисел.

Приклад:

import random

sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))

3. Пошук елемента в відсортованій базі даних

Знайти запис у відсортованій базі даних за ключовим полем.

Приклад:

database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
    left, right = 0, len(db) - 1
    while left <= right:
        mid = (left + right) // 2
        if db[mid]["id"] == target_id:
            return db[mid]
        elif db[mid]["id"] < target_id:
            left = mid + 1
        else:
            right = mid - 1
    return None

target_id = 54321
print(binary_search_db(database, target_id))