2. Пошукові алгоритми

Перелік алгоритмів, що розглядаються

  • лінійний пошук;
  • лінійний пошук з бар'єром;
  • бінарний пошук.

Короткі теоретичні відомості

Питання для повторення

  1. Способи заповнення одновимірних масивів.
  2. Виведення одновимірного масиву на екран.

Постановка задачі

Задано масив записів, одне поле яких виконує роль ключа. Необхідно знайти індекс, для якого значення ключового поля відповідного запису дорівнює заданому значенню, або вивчети повідомлення про відсутність такого поля.

Опис алгоритмів

Розглядається пошук ключа Key у масиві a цілих чисел, занумерованих від 0 до N-1.

1.Лінійний пошук

Ідея
Проглядати почергово елементи масиву, доки не буде знайдено шуканий елемент або не убде досягнуто кінець масиву.
Псевдокод
i=0
поки (i < N  і a[i] != Key)  
   { i=i+1}
якщо i=N
   то елемент відсутній
   інакше елемент має номер і

2. Лінійний пошук з бар'єром

Ідея
Як і у попередньому випадку, алементи проглядаються по черзі, але для зменшення кількості порівнянь після останнього елемента додається елемент з ключем, що дорівнює шуканому значенню.
Псевдокод
a[N] = Key; i = 0
поки (a[i] != Key)  
   { i = i+1}
якщо i = N   
   то елемент відсутній
   інакше елемент має номер і

3. Бінарний пошук

Ідея
Пошук реалізується в упорядкованому масиві. Шукане значення слід порівняти з ключем середнього елементу, у результаті цього порівняння визначити, у якій половині масиву знаходиться шуканий ключ, і знову застосувати ту саму процедуру до половини масиву. Процес припиняється, коли буде знайдено елемент, або коли "довжина" таблиці стане менше 1.
Псевдокод
L = 0; R = N-1
поки L < R
{
   m =(L+R) / 2
   якщо a[m] < Key
     то L = m+1
     інакше  R = m
}
якщо a[R] = Key
   то елемент має номер R 
   інакше елемент відсутній

Завдання для виконання

Постановка задачі

Скласти програми, що реалізують різні алгоритми пошуку, і зберегти їх у власній папці. Програми повинні забезпечувати:
  • автоматичну генерацію масиву цілих чисел (кількість елементів масиву вказується користувачем) та виведення його на екран;
  • пошук введеного користувачем числа у масиві за певним алгоритмом;
  • підрахунок кількості порівнянь у процесі пошуку елемента.

Технічні умови

  • кількість елементів у масиві не перевищує 50;
  • елементи масиву є невід'ємними цілими числами, що не перевищують 255.

Хід роботи

  1. Скласти програму lin.cpp, що реалізує лінійний пошук.
  2. Протестувати роботу програми. Для цього запустити програму для кількості елементів масиву від 10 до 50 з кроком 10. За результатами тестів заповнити таблицю
    Кількість елементів Результат пошуку* Кількість порівнянь
    10    
    20    
    30    
    40    
    50    
    *Як результат пошуку вказати, чи знайдено елемент, і якщо знайдено, то вказати відповідний індекс. У ході тестування передбачити одержання різних результатів пошуку.
  3. Створіть копію програми, ім'я lin2.cpp. Внесіть у програму зміни, забезпечивши реалізацію лінійного пошуку з бар'єром.
  4. Виконавши програму в покроковому режимі, заповнити таблицю виконання алгоритму для масиву 6 чисел
    i a[i] != Key i=N
         
  5. Скласти програму bin.cpp, що реалізує бінарний пошук. Для генерації впорядкованого масиву можна використати фрагмент, наведений нижче:
    randomize();
    a[0]=random(d);
    for (i=1; i<n;i++)
    {
       a[i]=a[i-1]+random(d);
    }
    Тут d — константа, що задає максимально можливий крок між сусідніми елементами масиву.
  6. Виконавши програму в покроковому режимі, заповнити таблицю виконання алгоритму для масиву 6 чисел.
    L R L < R m a[m]<Key a[R]=Key
       

Запитання для самоконтролю

  1. У чому полягає ідея лінійного пошуку? Сформулюйте умову припинення перегляду елементів.
  2. Які переваги в алгоритмі лінійного пошуку надає використання бар'єра? Як реалізується бар'єр?
  3. У якому випадку може використовуватися бінарний пошук? У чому його основна ідея?
  4. Сформулюйте алгоритм бінарного пошуку.