Лекція 12 Послідовний пошук

ПОШУК ДАНИХ.

Задача пошуку виникла пізніше, ніж задача сортування. Поява її спричинена головним чином появою автоматизованих інформаційних систем АІС, які будуються на основі комп‘ютерів.

Розглянемо звичайну пошукову задачу: як знаходити дані, що зберігаються в пам‘яті комп‘ютера за певною ідентифікацією.

Наприклад, в обчислювальній задачі потрібно знайти f(х), маючи значення x і таблицю значень функції f(x); у лінгвістичних задачах може цікавити англійський еквівалент відповідного слова.

Взагалі будемо припускати, що зберігається множина з n записів i необхідно визначити місцезнаходження відповідного запису. Розглянемо ряд алгоритмів пошуку і наведемо їх короткі характеристики, а також рекомендації застосування.

Послідовний пошук

Найпростішим методом пошуку певного запису, що знаходиться у невпорядкованій таблиці, є послідовний перегляд кожного запису, доки не буде виявленого злиття (співпадіння) з шуканим. Такий метод називають послідовним або лінійним пошуком.

Алгоритм L.

Таблиця містить п записів R₁,..., R_п з ключами k₁,..., k_п. Необхідно знайти запис iз заданим ключем k.

L1. Ініціалізація індексу проходження таблиці: і=1.

L2. Якщо k=k_i - кінець успішний; якщо ні, перехід на L3.

L3. Зміна індексу і =i+1.

L4. Перевірка умови i<n? Так: перехід на L 2. Ні - кінець неуспішний.

Ефективність алгоритму можна оцінити, підрахувавши кількість виконаних порівнянь тих значень ключів, які приймають участь у пошуку. Середня кількість таких порівнянь дорівнює величині п. Таким чином асимптоматична складність алгоритму - O (n). У зв’язку з малою ефективністю в порівнянні з іншимиалгоритмами лінійний пошук зазвичай використовують лише тоді, коли відрізок пошукової системи містить дуже мало елементів, однак лінійний пошук не вимагає додаткової пам’яті або аналізу функції, так що може працювати в потоковому режимі при безпосередньому отриманні даних з будь-якого джерела. Так само, лінійний пошук часто використовується у вигляді лінійних алгоритмів пошуку максимуму (мінімуму).

Приклад програмної реалізації.

Вихідний код програмної реалізації алгоритму лінійного пошуку на мові програмування C має наступний вигляд:

int* search(int *arr, int cnt, int req)

{

for (int i = 0; i < cnt; i++)

if (arr[i] == req)

return arr + i;

return NULL;

}