Новости
Анотація: В лекції розглядаються визначення та класифікація алгоритмів пошуку в лінійних структурах даних, опису і приклади реалізацій алгоритмів послідовного пошуку, пошуку з бар'єром, бінарного пошуку, наводиться оцінка трудомісткості алгоритмів пошуку в лінійних структурах.
Мета лекції: вивчити основні алгоритми пошуку в лінійних структурах і навчитися вирішувати завдання пошуку в лінійних структурах на основі алгоритмів послідовного та бінарного пошуку.
Одним з найважливіших дій зі структурованою інформацією є пошук. Пошук - процес знаходження конкретної інформації в раніше створеному безлічі даних. Зазвичай дані представляють собою записи, кожна з яких має хоча б один ключ. Ключ пошуку - це поле записи, за значенням якого відбувається пошук. Ключі використовуються для відмінності одних записів від інших. Метою пошуку є знаходження всіх записів (якщо вони є) з даними значенням ключа.
Структуру даних, в якій проводиться пошук, можна розглядати як таблицю символів (таблицю імен або таблицю ідентифікаторів) - структуру, яка містить ключі і дані, і допускає дві операції - вставку нового елемента і повернення елемента із заданим ключем. Іноді таблиці символів називають словниками по аналогії з добре відомою системою упорядкування слів в алфавітному порядку: слово - ключ, його тлумачення - дані.
Пошук є одним з найбільш часто зустрічаються дій в програмуванні. Існує безліч різних алгоритмів пошуку, які принципово залежать від способу організації даних. У кожного алгоритму пошуку є свої переваги і недоліки. Тому важливо вибрати той алгоритм, який найкраще підходить для вирішення конкретного завдання.
Поставимо задачу пошуку в лінійних структурах. Нехай задано безліч даних, яке описується як масив, що складається з певної кількості елементів. Перевіримо, чи входить заданий ключ в даний масив. Якщо входить, то знайдемо номер цього елемента масиву, тобто, визначимо перше входження заданого ключа (елемента) в вихідному масиві.
Таким чином, визначимо загальний алгоритм пошуку даних:
Крок 1. Обчислення елемента, що часто передбачає отримання значення елемента, ключа елемента і т.д.
Крок 2. Порівняння елемента з еталоном або порівняння двох елементів (в залежності від постановки задачі).
Крок 3. Перебір елементів безлічі, тобто проходження за елементами масиву.
Основні ідеї різних алгоритмів пошуку зосереджені в методах перебору і стратегії пошуку.
Розглянемо основні алгоритми пошуку в лінійних структурах більш докладно.
Послідовний (лінійний) пошук
Послідовний (лінійний) пошук - це найпростіший вид пошуку заданого елемента на деякій множині, здійснюваний шляхом послідовного порівняння чергового розглянутого значення з шуканим до тих пір, поки ці значення не співпадуть.
Ідея цього методу полягає в наступному. Безліч елементів проглядається послідовно в деякому порядку, що гарантує, що будуть переглянуті всі елементи безлічі (наприклад, зліва направо). Якщо в ході перегляду безлічі буде знайдений шуканий елемент, перегляд припиняється з позитивним результатом; якщо ж буде переглянуто всі безліч, а елемент не буде знайдений, алгоритм повинен видати негативний результат.
Алгоритм послідовного пошуку
Крок 1. Вважаємо, що значення змінної циклу i = 0.
Крок 2. Якщо значення елемента масиву x [i] дорівнює значенню ключа key, то повертаємо значення, рівне номеру шуканого елемента, і алгоритм завершує роботу. В іншому випадку значення змінної циклу збільшується на одиницю i = i + 1.
Крок 3. Якщо i <k, де k - число елементів масиву x, то виконується крок 2, в іншому випадку - робота алгоритму завершена і повертається значення рівне -1.
При наявності в масиві декількох елементів зі значенням key даний алгоритм знаходить тільки перший з них (з найменшим індексом).
int LinearSearch (int * x, int k, int key) {int i = 0; for (i = 0; i <k; i ++) if (x [i] == key) break; return i <k? i: 1; }
Час виконання даного алгоритму пошуку для дійсних чисел , Де n - кількість елементів множини, а - точність. Пошук на дискретній множині з n елементів здійснюється в гіршому випадку за n ітерацій, а в середньому цей алгоритм вимагає n / 2 ітерацій циклу. Отже, тимчасова складність послідовного пошуку пропорційна O (n). Ніяких обмежень на порядок елементів в масиві даний алгоритм не накладаються.
Недоліком даного алгоритму пошуку є те, що в гіршому випадку здійснюється перегляд всього масиву. Тому даний алгоритм використовується, якщо безліч містить невелику кількість елементів.
Переваги послідовного пошуку полягають в тому, що він простий в реалізації, не вимагає сортування значень безлічі, додаткової пам'яті і додаткового аналізу функцій. Отже, може працювати в потоковому режимі при безпосередньому отриманні даних з будь-якого джерела.
Існує модифікація алгоритму послідовного пошуку, яка прискорює пошук. Ця модифікація є невеликим удосконаленням розглянутого алгоритму пошуку.
Ідея пошуку з бар'єром полягає в тому, щоб не перевіряти кожен раз в циклі умова, пов'язане з межами безлічі. Це можна забезпечити, встановивши в даному безлічі так званий бар'єр. Під бар'єром розуміється будь-який елемент, який задовольняє умовам пошуку. Тим самим буде обмежено зміна індексу.
Вихід з циклу, в якому тепер залишається тільки умова пошуку, може відбутися або на знайденому елементі, або на бар'єрі. Існує два способи установки бар'єру: додатковим елементом або замість крайнього елемента масиву.
// опис функції послідовного пошуку з бар'єром int LinearSearchWithBarrier (int * x, int k, int key) {x = (int *) realloc (x, (k + 1) * sizeof (int)); x [k] = key; int i = 0; while (x [i]! = key) i ++; return i <k? i: 1; }
Зауважимо, що пошук з бар'єром працює швидше, але тимчасова складність алгоритму залишається такою ж O (n), де n - кількість елементів множини. Набагато більший інтерес представляють методи, не тільки працюють швидко, але і реалізують алгоритми з меншою складністю.
Бінарний (двійковий) пошук
Бінарний (двійковий, дихотомический) пошук - це пошук заданого елемента на впорядкованій множині, здійснюваний шляхом кількаразового ділення цієї множини на дві частини таким чином, що шуканий елемент потрапляє в одну з цих частин. Пошук закінчується при збігу шуканого елемента з елементом, який є кордоном між частинами безлічі або при відсутності шуканого елемента.
Бінарний пошук застосовується до відсортованим безлічам і полягає в послідовному розбитті безлічі навпіл і пошуку елемента тільки в одній половині на кожній ітерації.
Таким чином, ідея цього методу полягає в наступному. Пошук потрібного значення серед елементів упорядкованого масиву (по зростанню або по спадаючій) починається з визначення значення центрального елемента цього масиву. Значення даного елемента порівнюється з шуканим значенням і залежно від результатів порівняння робляться певні дії. Якщо шукане і центральне значення виявляються рівні, то пошук завершується успішно. Якщо шукане значення менше центрального або більше, то формується масив, що складається з елементів, що знаходяться зліва чи справа від центрального відповідно. Потім пошук повторюється в новому масиві ( Мал. 37.1 ).
Алгоритм бінарного пошуку
Крок 1. Визначити номер середнього елемента масиву middle = (high + low) / 2.
Крок 2. Якщо значення середнього елемента масиву одно шуканого, то повертаємо значення, рівне номеру шуканого елемента, і алгоритм завершує роботу.
Крок 3. Якщо шукане значення більше значення середнього елемента, то візьмемо в якості масиву всі елементи праворуч від середнього, інакше візьмемо в якості масиву всі елементи зліва від середнього (в залежності від характеру впорядкованості). Перейдемо до Кроку 1.
У масиві може зустрічатися кілька елементів зі значеннями, рівними ключу. Даний алгоритм знаходить перший співпав з ключем елемент, який в порядку проходження в масиві може бути ні першим, ні останнім серед рівних ключу. Наприклад, в масиві чисел 1, 5, 5, 5, 5, 5, 5, 7, 8 з ключем key = 5 співпаде елемент з порядковим номером 4, який не належить ні до першого, ні до останнього.
Існують дві модифікації даного алгоритму для пошуку першого і останнього входження. Все залежить від того, як вибирається середній елемент: округленням в меншу або більшу сторону. У першому випадку середній елемент відноситься до лівої частини масиву, а в другому - до правої.
Мал.37.1.
Демонстрація алгоритму бінарного пошуку // опис функції бінарного пошуку int BinarySearch (int * x, int k, int key) {bool found = false; int high = k - 1, low = 0; int middle = (high + low) / 2; while (! found && high> = low) {if (key == x [middle]) found = true; else if (key <x [middle]) high = middle - 1; else low = middle + 1; middle = (high + low) / 2; } Return found? middle: -1; }
У процесі роботи алгоритму бінарного пошуку розмір фрагмента, де цей пошук повинен тривати, щораз зменшується приблизно в два рази. Це забезпечує складність алгоритму пропорційну O (log n), де n - кількість елементів множини.
Час виконання алгоритму бінарного пошуку: якщо функція має речовинний аргумент, знайти рішення з точністю до можна за час , А якщо аргумент дискретний, то пошук рішення займе 1 + log n часу.
Перевагою даного алгоритму є відносна швидкість виконання пошуку, в порівнянні з алгоритмом послідовного пошуку. Недолік полягає в тому, що бінарний пошук може застосовуватися тільки на впорядкованій множині.
Ключові терміни
Бінарний (двійковий, дихотомический) пошук - це пошук заданого елемента на впорядкованій множині, здійснюваний шляхом кількаразового ділення цієї множини на дві частини таким чином, що шуканий елемент потрапляє в одну з цих частин.
Ключ пошуку - це поле записи, за значенням якого відбувається пошук
Пошук - це процес знаходження конкретної інформації в раніше створеному безлічі даних.
Пошук з бар'єром - це модифікація алгоритму послідовного пошуку, що прискорює процес шляхом визначення граничного елемента.
Послідовний (лінійний) пошук - це найпростіший вид пошуку заданого елемента на деякій множині, здійснюваний шляхом послідовного порівняння чергового розглянутого значення з шуканим до тих пір, поки ці значення не співпадуть.
короткі підсумки
- Одним з найважливіших дій зі структурованою інформацією є пошук.
- Існує безліч різних алгоритмів пошуку, які принципово залежать від способу організації даних. У кожного алгоритму пошуку є свої переваги і недоліки.
- Послідовний (лінійний) пошук є найпростішим видом пошуку заданого елемента на деякій множині, здійснюваним шляхом послідовного порівняння чергового розглянутого значення з шуканим до тих пір, поки ці значення не співпадуть.
- Існує модифікація алгоритму послідовного пошуку, яка прискорює пошук шляхом установки в розглянутому безлічі бар'єру.
- Бінарний (двійковий, дихотомический) пошук є пошуком заданого елемента на впорядкованій множині, здійснюваним шляхом кількаразового ділення цієї множини на дві частини таким чином, що шуканий елемент потрапляє в одну з цих частин. Бінарний пошук застосовується до відсортованим безлічам.
- Перевагою бінарного пошуку є більш низька трудомісткість в порівнянні з послідовним пошуком. Недолік бінарного пошуку полягає в тому, що він застосовується лише на відсортованих множинах.