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

2.1 Визначення бінарного пошуку та його основні концепції

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

Основні концепції:

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

Важливо! Для бінарного пошуку потрібен відсортований масив.

Для правильної роботи бінарного пошуку вхідні дані мають бути відсортовані за зростанням. Це основна і єдина вимога, оскільки алгоритм спирається на той факт, що елементи масиву впорядковані. Завдяки цьому він може ефективно виключати половину елементів на кожному кроці пошуку.

Приклад відсортованого масиву:

sorted_array = [1, 3, 5, 7, 9, 11, 13]

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

Принцип роботи бінарного пошуку:

1. Ініціалізація: Встановити початкові межі пошуку (ліва і права межі масиву).
2. Вибір середнього елемента: Знайти індекс середнього елемента масиву.
3. Порівняння: Порівняти середній елемент з шуканим значенням.
4. Оновлення меж:
   1. Якщо середній елемент дорівнює шуканому значенню, повернути його індекс.
   2. Якщо шукане значення менше середнього елемента, оновити праву межу пошуку.
   3. Якщо більше — оновити ліву межу.
5. Повторення: Повторювати кроки 2-4 до знаходження елемента або поки ліва межа не стане більшою за праву.

Пошаговий алгоритм:

1. Ініціалізація: Встановити left на 0 і right на len(arr) - 1.
2. Вычислить средний элемент: mid = (left + right) // 2
3. Порівняти з цільовим елементом:
   1. Якщо arr[mid] == target, повернути mid
   2. Якщо arr[mid] < target, оновити left = mid + 1
   3. Якщо arr[mid] > target, оновити right = mid - 1
4. Повторити: Повернутися до кроку 2 доти, поки left <= right
5. Якщо елемент не знайдено: Повернути -1

Ітеративна реалізація бінарного пошуку в Python:

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

2.3 Часова складність бінарного пошуку O(log n)

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

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

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

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

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"Елемент {target} знайдено на індексі {index}")  # Вивід: Елемент 7 знайдено на індексі 3

# Алгоритм виконав 3 кроки (логарифм від 7 елементів) для знаходження елемента, 
# що відповідає O(log n)

Графічне представлення складності:

Уяви собі масив із 16 елементів.

Припустимо, ми шукаємо елемент 15, тоді кроки будуть такі:

Перший крок. Перевірити середній елемент (8 елементів залишається).

Другий крок. Перевірити середній елемент у залишеній половині (4 елементи залишаються).

Третій крок. Перевірити середній елемент у залишеній половині (2 елементи залишаються).

Четвертий крок. Перевірити останній елемент (1 елемент залишається).

У результаті алгоритм виконає 4 кроки для масиву із 16 елементів, що відповідає логарифму за основою 2 від 16, тобто, log2(16) = 4. Це і є логарифмічна складність O(log n).