Тема 3. Методи пошуку в одновимірному масиві.

Питання теми та основні терміни.

Загальна характеристика операцій пошуку.

Основні методи пошуку.

Метод простого пошуку, метод пошуку з бар’єром, зразок пошуку, бінарний пошук,

Інформаційні матеріали теми

1. Загальна характеристика операцій пошуку.

При розв’язанні завдань часто виникає потреба у знаходженні серед набору даних значення з певними властивостями. Наприклад. Потрібно знайти всіх студентів, що одержали оцінку “відмінно” за контрольну роботу,  номер телефону абонента за його домашньою адресою, тощо. Для виконання таких дій призначені алгоритми пошуку. В загальному випадку пошук можна здійснювати за декількома критеріями, тобто, задавати складені умови пошуку. Крім того. Самі дані можуть бути організовані й різні структури (масиви, записи, файли), що також вносить свої особливості в проведення пошуку. Саме завдання пошуку також може мати різні формулювання:

· знайти перший елемент структури даних із заданими властивостями;

· знайти всі елементи структури даних із заданими властивостями;

· перевірити наявність в структурі даних елементів  із заданими властивостями.

Хоча формулювання і цілі наведених завдань різні. Всі вони розв’язуються за однаковими підходами. Далі буде розглянута сутність операцій пошуку даних. При цьому здійснимо такі припущення:

1) в ролі структури даних для розгляду алгоритмів пошуку оберемо одновимірний цілочисельний масив;

2) пошук буде проводитись до  першого знаходження елементу із заданими властивостями або переконання, що заданий елемент відсутній;

3) результатом пошуку  буде номер , під яким знаходиться шуканий елемент, або повідомлення, що заданий елемент в масиві відсутній;

4) в головній програмі діє такий опис даних

const n=...;

{кількість елементів масиву визначається користувачем}

type

massiv = array[1..n] of integer;

var

a:massiv;

i:integer;

5) для практичної реалізації методів пошуку заповнення масиву здійснюється випадковими числами.

Шуканий в масиві елемент  назвемо зразком пошуку.