Перейти до змісту

ЛР12. Лінійний і двійковий пошук: контракти, передумови та обсяг роботи

Коротко про роботу

В одній роботі порівнюються два контракти пошуку: послідовна перевірка невпорядкованих даних і звуження інтервалу у вже впорядкованій послідовності. Варіант визначає STUDENT_X.

Відкрити робочий зошит Як виконувати лабораторні

1. Умова

В одній роботі порівнюються два контракти пошуку: послідовна перевірка невпорядкованих даних і звуження інтервалу у вже впорядкованій послідовності.

Перша комірка зошита лише показує значення вашого STUDENT_X разом із типами. Вона не оголошує і не створює предметні змінні. У коді кожного завдання перенесіть потрібні значення та самостійно оголосіть/створіть відповідні змінні.

2. Що треба знати

Робота виконується після Л1–Л7. Потрібні поняття:

  1. лінійний пошук
  2. умова функції
  3. операція порівняння
  4. O(n)
  5. передумова впорядкованості
  6. двійковий пошук
  7. O(log n)
  8. інваріант активного інтервалу

Межа матеріалу

Використовуйте поняття, вивчені до Л1–Л7. Не сортуйте дані перед лінійним пошуком і не підміняйте власні реалізації викликами std::find або бібліотечної функції двійкового пошуку.

3. Варіант, вхідні дані та результат

У зошиті заповніть STUDENT_NAME, STUDENT_GROUP і STUDENT_X від 1 до 30.

Вхідні дані

Поле Тип Зміст
linear_values std::vector<int> невпорядкована послідовність для лінійного пошуку
linear_target int ціль лінійного пошуку
binary_values std::vector<int> впорядкована послідовність для двійкового пошуку
binary_target int ціль двійкового пошуку
unsorted_probe std::vector<int> копія двійкової послідовності з локальним порушенням порядку

Поля результату

Поле Зміст
linear_found_index перша позиція або -1 для лінійного пошуку
linear_comparisons кількість порівнянь із ціллю у лінійному пошуку
linear_found ознака успішного лінійного пошуку
binary_found_index позиція або -1 для двійкового пошуку
binary_iterations кількість перевірених mid
mid_trace послідовність індексів середини

Назви полів результату не змінюйте. Перша комірка лише показує значення варіанта і не оголошує предметні змінні. Перед розв’язанням кожного завдання самостійно оголосіть потрібні вхідні змінні з показаними значеннями. Власні та результуючі змінні також оголошуйте звичайно, як у лекційних прикладах. Обчислення виконуйте у блоці { ... }; код над блоком використовуйте лише там, де це позначено. Наприкінці блока вже є службовий рядок самоперевірки для контрольних полів — його не потрібно писати або змінювати. Формат std::cout обирайте за змістом завдання: спеціального формату для самоперевірки немає.

4. Терміни і правила

Терміни

  • лінійний пошук — послідовна перевірка елементів від початку до першого збігу.
  • порівняння — одна перевірка element == target; саме такі перевірки треба рахувати.
  • передумова — умова, яка має бути істинною до запуску алгоритму.
  • напіввідкритий інтервал [low, high) — індекси від low включно до high невключно.
  • середній індекс — індекс середини активного інтервалу.

Правила

  1. linear_found_index — нульовий індекс першого елемента, рівного linear_target; для відсутньої цілі використовуйте -1.
  2. linear_comparisons рахує лише перевірки виду «поточний елемент дорівнює linear_target».
  3. Пошук завершується після першого збігу або після перевірки останнього елемента.
  4. linear_found має бути true рівно тоді, коли linear_found_index не дорівнює -1.
  5. binary_values уже впорядковано за зростанням. Основний пошук працює з напіввідкритим інтервалом [low, high).
  6. На кожній ітерації mid = low + (high - low) / 2 з цілочисельним діленням.
  7. mid_trace зберігає кожний перевірений індекс mid у фактичному порядку.
  8. unsorted_probe призначений лише для демонстрації порушення передумови. Контрольні поля обчислюються для binary_values.

5. Завдання

Завдання 1

Реалізуйте лінійний пошук першого linear_target у linear_values. Запишіть linear_found_index, linear_found і кількість порівнянь у linear_comparisons.

Завдання 2

Запустіть лінійний пошук для першого елемента, початкового linear_target і відсутнього значення. Для кожного випадку виведіть індекс, кількість порівнянь і результат пошуку.

Завдання 3

Для трьох перевірок лінійного пошуку запишіть очікувано → отримано. Після цього знову обчисліть контрольні поля для початкового linear_target.

Завдання 4

Реалізуйте двійковий пошук у binary_values для binary_target. Запишіть індекс у binary_found_index, а кількість перевірок — у binary_iterations.

Завдання 5

Під час двійкового пошуку додавайте кожний перевірений індекс mid у mid_trace.

Завдання 6

Запустіть двійковий пошук для unsorted_probe з тією самою binary_target. Поясніть одним реченням, чому без впорядкування результат не гарантований.

6. Перевірка і здача

  1. Запустіть самоперевірку та виправте помилки.
  2. Перезапустіть ядро і виконайте роботу ще раз від початку.
  3. Збережіть .ipynb і PDF з кодом та результатами.

Назва PDF: LR12_Прізвище_Група_VNN.pdf.