18 травня о 18:00Вебінар: Інтерактивний урок математики: алгоритми та приклади створення дидактичних матеріалів

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

Про матеріал
В презентації описана реалізація бінарного пошуку в мовах програмування javascript та python
Зміст слайдів
Номер слайду 1

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

Номер слайду 2

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

Номер слайду 3

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

Номер слайду 4

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

Номер слайду 5

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

Номер слайду 6

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

Номер слайду 7

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

Номер слайду 8

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

Номер слайду 9

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

Номер слайду 10

Алгоритм на python

Номер слайду 11

Алгоритм на Javascript

Номер слайду 12

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

Номер слайду 13

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

Номер слайду 14

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

Номер слайду 15

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

Номер слайду 16

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

Номер слайду 17

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

Номер слайду 18

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

pptx
Додано
17 березня
Переглядів
62
Оцінка розробки
Відгуки відсутні
Безкоштовний сертифікат
про публікацію авторської розробки
Щоб отримати, додайте розробку

Додати розробку