ЛР14. Двійковий пошук і передумова впорядкованості

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

Каталог уже впорядкований. Пошук звужує активний інтервал після кожної перевірки середини. Варіант визначає STUDENT_X.

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

1. Умова

Каталог уже впорядкований. Пошук звужує активний інтервал після кожної перевірки середини.

Усі обчислення виконуйте з даними свого STUDENT_X. Значення варіанта друкує перша комірка зошита.

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

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

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

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

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

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

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

Вхідні дані

Поле	Зміст
values	впорядкована послідовність
target	ціль
unsorted_probe	та сама послідовність із локальним порушенням порядку

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

Поле	Зміст
found_index	позиція або -1
iterations	кількість перевірених mid
mid_trace	послідовність індексів середини

Назви полів результату не змінюйте.

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

Терміни

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

Правила

1. values уже впорядковано за зростанням. Основний пошук працює з напіввідкритим інтервалом [low, high).
2. На кожній ітерації mid = low + (high - low) / 2 з цілочисельним діленням.
3. mid_trace зберігає кожний перевірений індекс mid у фактичному порядку.
4. unsorted_probe призначений лише для демонстрації порушення передумови. Контрольні поля обчислюються для values.

5. Завдання

Завдання 1

Реалізуйте двійковий пошук у values. Запишіть індекс у found_index, а кількість перевірок — у iterations.

Завдання 2

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

Завдання 3

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

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

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

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