Конструктор уроків
Цілі:
навчальна: бінарний пошук, модифікація алгоритму
розвивальна: розвивати логічне мислення; формувати вміння діяти за інструкцією, планувати свою діяльність, аналізувати i робити висновки;
виховна: виховувати інформаційну культуру учнів, уважність, акуратність, дисциплінованість.
2
3
4
Алгоритм бінарного пошуку застосовується до відсортованого масиву. Якщо відсортований масив містить дублікати (елементи, які повторюються, наприклад, у масиві [2, 4, 4, 8, 11, 14] повторюється число 4), тоді модифікації алгоритму бінарного пошуку дозволяють обчислити перше і останнє входження такого елемента.
Знайти елемент Х в масиві | Знайти перше входження елементу Х в масиві |
|
Увага: права межа зменшується, якщо mid є більшим або рівним елементу Х |
Знайти елемент Х в масиві | Знайти останнє входження елементу Х в масиві |
|
Увага: ліва межа збільшується, якщо mid є меншим або рівним елементу Х |
5
Задача. Бінарний пошук-1
Ознайомитись з умовою задачі на EOlymp Порівняти з умовою задачі Бінарний пошук
По аналогії з програмою до задачі Бінарний пошук скласти програму до задачі Бінарний пошук-1.
Алгоритм
1) прочитати n та q
2) прочитати масив а
3) для кожного запиту q (в циклі виконати пункти 4-8)
4) прочитати елемент Х
5) за допомогою алгоритму бінарного пошуку знайти перше входження елемента Х в масив А
6) 
7) інакше - за допомогою алгоритму бінарного пошуку знайти останнє входження елемента Х в масив А
8) 
Надіслати скріншот програми та результатів тестування на сервері.
Увага: оскільки Python-програма працює повільніше, ніж програми, наприклад, на мові С, С++, то програма має пройти всі тести крім 7-10 та 13, де розміщені великі вхідні дані.
.png)
6
Домашнє завдання
Вивчити команду сортування на мові Python та модифікації алгоритму бінарного пошуку.
Рефлексія від 3 учнів
Сподобався:
Так: 3
Ні: 0
Зрозумілий:
Так: 3
Ні: 0
Потрібні роз'яснення:
Ні: 3
Так: 0
