Конструктор уроків
Цілі:
навчальна: Двійковий пошук. Розв'язування задач
розвивальна: розвивати логічне мислення; формувати вміння діяти за інструкцією, планувати свою діяльність, аналізувати i робити висновки;
виховна: виховувати інформаційну культуру учнів, уважність, акуратність, дисциплінованість.
2
3
4
5
Виконати завдання. Надіслати скріншот
.png)
6
Задача. Бінарний пошук
Ознайомитись з умовою задачі на EOlymp
Скласти програму
Підказки:
Одним з найшвидших алгоритмів для пошуку елементів у відсортованому масиві є бінарний пошук. Цей алгоритм зменшує кількість порівнянь, які потрібні для пошуку елемента, в порівнянні з лінійним пошуком.
Основна ідея бінарного пошуку полягає у поділі відсортованого масиву на дві частини та порівнянні шуканого елемента з середнім елементом масиву. Якщо шуканий елемент менший за середній, то пошук продовжується у першій половині масиву, в іншому випадку - у другій половині. Пошук продовжується, доки елемент не знайдений або доки не залишиться один елемент у частині масиву, в якій здійснюється пошук.
n, q = map(...) # прочитати два числа в рядку
a = list(map(...)) # прочитати масив чисел в рядку
for step in range(0, q, 1): # цикл по запитах
ccccx = i...t(input()) # прочитати число Х
ccccl, r = 0, n-1 # встановити межі інтервалу
# алгоритм бінарного пошуку
ccccwhile r >= l: №
ccccccccm = (...) // 2
ccccccccif a[m] == x: break
ccccccccelif a[m] ... x: l =... + ...;
ccccccccelse: r = ... - ...;
# аналіз відповіді алгоритму: перевірка наявності Х числа в масиві А
ccccif a[m] == x: print("YES")
ccccelse: print("NO")
Надіслати скріншот програми та результатів тестування на сервері.
7
Домашнє завдання
Вивчити етапи алгоритму двійкового пошуку
Рефлексія від 8 учнів
Сподобався:
Так: 7
Ні: 1
Зрозумілий:
Так: 7
Ні: 1
Потрібні роз'яснення:
Ні: 7
Так: 1
