Embedded Files
Бінарний пошук
Які, на вашу думку, особливості пошуку елементів в упорядкованому масиві слід враховувати з метою прискорення процесу пошуку?
Існує також бінарний пошук, або половинно-інтервальний пошук, однак він працює лише з відсортованими елементами, один з найшвидших алгоритмів, який повторно порівнює пошуковий елемент з центральним елементом заданої структури, якщо знайшов то кінець, якщо ні, то порівнює елементи та продовжує пошук в лівій чи правій частині структури даних поки не знайде потрібний.
Алгоритм
1.Вибрати середній елемент A[c] і порівняти з X.
2.Якщо X = A[c], знайшли (вихід).
3.Якщо X < A[c], шукати далі в першій половині.
4.Якщо X > A[c], шукати далі в другій половині.
Припустимо, нам потрібно щось знайти в телефонній книзі (або в словнику) на літеру "К". Можна розпочати із першої сторінки і поступово рухатись до К. А можна відкрити книгу приблизно посередині, і таким чином швидше дійти до потрібного місця.
Варто скористатися бінарним пошуком, алгоритм якого полягає у наступному. На вході маємо впорядковану послідовність елементів. Якщо шуканий елемент присутній у списку, то на виході отримаємо його порядковий номер, інакше отримаємо null. За рахунок відкидання половини можливих варіантів на кожному із кроків алгоритму, ми дуже швидко отримаємо потрібний результат. Так, у словнику зі 100 елементів ми гарантовано отримаємо результат за 7 кроків:
Розглянемо розв'язання Задачі 1 (з уроку 38) за допомогою алгоритму бінарного пошуку:
Знайти елемент масиву, рівний X, або встановити, що його немає.
Нехай дано масив а[1], ..., а[n], елементи якого впорядковані за зростанням їхніх значень, і ключове значення х, яке потрібно знайти в масиві. Пошук будемо здійснювати методом половинного ділення.
Сутність алгоритму бінарного пошуку така:
Приклад 3. Нехай дано масив комп’ютерних термінів: алгоритмізація, біт, змінна, масив, миша, файл. Розробимо програму визначення, чи є в цьому масиві термін, який після запуску програми вводиться з клавіатури. Розглянемо алгоритм розв’язування.
Один із варіантів виконання програми:
Практичне завдання (виконайте самостійно)
Практичне завдання (виконайте самостійно)
Увага! Під час роботи з комп'ютером дотримуйтеся вимог безпеки життєдіяльності та санітарно-гігієнічних норм.
Завдання 1. Розробіть програму створення масиву, що містить 10 випадкових чисел у діапазоні від 3 до 9 і визначення, чи є у ньому число 6.
Завдання 2. Дано масив рядків: ‘байт’, ‘принтер’, ‘процесор’, ‘монітор’. Розробіть програму визначення позиції слова, що уводиться з клавіатури.
Page updated
Google Sites
Report abuse