Презентація "Бінарний пошук"

Бінарнийпошук. Кузенко Ярослав 213 група

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

Алгоритм. Знаходимо індекс середнього елементу. Порівнюємо значення, яке шукаємо з середнім елементом масиву. Тут розглядаємо 3 можливі випадки:шукане значення = середньому елементу, тоді пошук завершено;шукане значення < середнього елементу, тоді здійснюємо пошук у першій половині масиву;шукане значення > середнього елементу, тоді здійснюємо пошук у першій половині масиву. Продовжуємо поки інтервал пошуку не перетвориться в одне число або поки не буде знайдений елемент.

Встановлюємо крайні межіВизначаємо середину масиву. Алгоритм бінарного пошуку

Mid < 9, тому наше число має бути у правій частині масиву

Пересуваємо ліву межу. Та знову визначаємо середину

9 < 12, тому переносимо праву межу

Ліва межа довінює 9. Пошук завершено

Оголошуємо відсортований масив. Встановлюємо ліву межу на початку масиву. Встановлюємо праву межу в кінці масиву. Вводимо число, що шукаємо. Встановлюємо середній елементtruefalsefalsetrue. Визначаємо куди посунути межу. Визначаємо чи є шукане число у масивіВиконуємо цикл поки межі не будуть розташовані поруч

Алгоритм на python

Алгоритм на Javascript

Порівняння швидкодії алгоритмів. Час затрачений на пошук 9 бінарним пошуком: 1,6 секунди

Час затрачений на пошук 9 лінійним пошуком: 1,8 секунди. Так ми утвердились, що бінарний пошук значно ефективніший за лінійний

Швидкість Роботи{5 C22544 A-7 EE6-4342-B048-85 BDC9 FD1 C3 A}Кількість ітерацій для пошуку числа в масивіБінарний пошук. Лінійний пошук757105001460051720025 Складність лінійного пошуку – O(n)Складнсть бінарного пошуку – O(log2n)

Складність алгоритму. Бінарний пошук вимагає єдиного проходу по масиву - O(n) але таким чином що він бере до уваги тільки певні елементи. Таким чином кількість елементів які будуть розглянуті вираховується простою формулою: log2 n. Отже складність алгоритму O(log n)

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

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

Дякую за увагу!