Практика: Алгоритми пошуку
Відпрацюємо лінійний та бінарний пошук, перевіримо, коли потрібне сортування, і повторимо складність алгоритмів.
1 Перевірка наявності
Є список nums = [1, 3, 7]. Який код правильно перевіряє, чи є число 3 у списку?
2 Лінійний пошук (код)
Напиши функцію linear_search(items, target), яка повертає індекс знайденого елемента або -1, якщо елемента немає.
3 Умова для бінарного пошуку
Що обов’язково має бути правдою, щоб бінарний пошук працював коректно?
4 Формула середини
Напиши рядок коду, який обчислює середній індекс між left та right (цілочисельно).
5 Складність
Вибери правильну пару: лінійний пошук і бінарний пошук (у найгіршому випадку).
Завдання для VS Code / IDLE
Реалізуйте ці задачі у файлі .py на своєму комп'ютері.
🔎 1) Функції пошуку
Реалізуйте linear_search і binary_search. Для бінарного пошуку додайте перевірку: якщо список не відсортований — спочатку відсортуйте (або виведіть попередження).
⏱️ 2) Лічильник кроків
Додайте змінну steps і порахуйте, скільки перевірок робить лінійний пошук та бінарний для списку з 1000 елементів.
🧠 3) Пошук максимуму
Напишіть алгоритм, який знаходить максимальне значення у списку без max(). Поясніть, чому це теж “пошук”.
Коли виконаєш всі завдання, зроби скріншот результатів та кодів і надішли вчителю в Classroom.