Інформатика – Поглиблений рівень

Прочитайте!

Існує також бінарний пошук, або половинно-інтервальний пошук, однак він працює лише з відсортованими елементами, один з найшвидших алгоритмів, який повторно порівнює пошуковий елемент з центральним елементом заданої структури, якщо знайшов то кінець, якщо ні, то порівнює елементи та продовжує пошук в лівій чи правій частині структури даних поки не знайде потрібний.

АЛГОРИТМ

1. Вибрати середній елемент A[c] і порівняти з X.
2.  Якщо X = A[c], знайшли (вихід).
3. Якщо X < A[c], шукати дальше в першій половині.
4. Якщо X > A[c], шукати дальше в другій половині.

Задача 1. Знайти елемент списку, рівний X, або встановити, що його немає.

Сутність алгоритму бінарного пошуку така.

Бінарний пошук можна застосовувати не лише для відшукання елементів впорядкованих масивів чи розв’язання рівнянь з монотонними функціями, але й для розв’язання різноманітних задач де необхідно знайти певне значення. Для розв’язання таких задач необхідно задати вихідну область пошуку, що визначається лівою та правою межами, перша з яких є заздалегідь меншою за відповідь, а права – більшою. Ця область пошуку (тобто відрізок [, ]) фактично і є впорядкованою множиною потенційних розв’язків серед яких потрібно обрати той, що задовольняє умову задачі. Бінарний пошук полягає у тому, що на кожному кроці алгоритму обчислюється значення визначеної умовою задачі характеристики у точці, що є серединою області пошуку і, залежно від отриманого значення, відбувається звуження області пошуку на ліву чи праву її підобласті. Описаний вище підхід називається бінарним пошуком по відповіді.

Розглянемо його детальніше на прикладі 2.

Сьогодні вранці журі вирішило додати у варіант олімпіади ще одну, Дуже Легку Задачу. Відповідальний секретар оргкомітету надрукував її умову в одному екземплярі, і тепер йому потрібно до початку олімпіади встигнути зробити ще копій. У його розпорядженні є два ксерокси, один з яких копіює аркуш за секунд, а другий за . (Дозволяється використовувати як один ксерокс, так і обидва одночасно. Можна копіювати не лише з оригінала, але і з копії.). Допоможіть йому вияснити, який мінімальний час для цього потрібно. Алгоритми і структури даних. Як було зазначено вище, розв’язання задачі необхідно почати з визначення вихідної області пошуку. Очевидно, що мінімальний час витрачений на друк не може бути меншим за нуль, а максимальний час – час необхідний для того, щоб надрукувати всі копії на одному ксероксі. Тут слід зауважити, що оскільки друк буде відбуватися на двох ксероксах одночасно, а спочатку є наявною лише один екземпляр умови, то першим кроком необхідно зробити ще один екземпляр умови, з якої почнеться друк на другому ксероксі. Цей випадок необхідно виокремити, оскільки він не потраплятиме під загальний підхід. Очевидно, що друк додаткового екземпляру варто здійснювати на швидшому ксероксі і займе цей процес min(, ) секунд (важливо не забути врахувати цей час у відповіді). Після цього лишиться надрукувати − 1 екземпляр умови. Отже, областю потенційних розв’язків буде відрізок [, ] = [0, ( − 1) max(, )]. Далі починає працювати бінарний пошук – вираховуємо середину області = + 2 та рахуємо скільки повних сторінок можна надрукувати за цей час використовуючи обидва ксерокси. Якщо кількість сторінок менша за − 1, то змінюємо нижню межу границі області пошуку, інакше – праву.

Розглянемо алгоритм бінарного пошуку на прикладі 3.

Програму реалізації алгоритму зображено на рис. 6.8.

Самостійне виконання вправ:

Завдання 1. Дано масив рядків: ‘байт’, ‘принтер’, ‘процесор’, ‘монітор’. Розробіть програму визначення позиції слова, що уводиться з клавіатури.