Новости

НОУ ІНТУЇТ | лекція | Алгоритми пошуку в лінійних структурах

  1. Послідовний (лінійний) пошук
  2. Бінарний (двійковий) пошук
  3. Ключові терміни
  4. короткі підсумки

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

Мета лекції: вивчити основні алгоритми пошуку в лінійних структурах і навчитися вирішувати завдання пошуку в лінійних структурах на основі алгоритмів послідовного та бінарного пошуку.

Одним з найважливіших дій зі структурованою інформацією є пошук. Пошук - процес знаходження конкретної інформації в раніше створеному безлічі даних. Зазвичай дані представляють собою записи, кожна з яких має хоча б один ключ. Ключ пошуку - це поле записи, за значенням якого відбувається пошук. Ключі використовуються для відмінності одних записів від інших. Метою пошуку є знаходження всіх записів (якщо вони є) з даними значенням ключа.

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

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

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

Таким чином, визначимо загальний алгоритм пошуку даних:

Крок 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 ітерацій, а в середньому цей алгоритм вимагає 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 часу можна за час , А якщо аргумент дискретний, то пошук рішення займе 1 + log n часу.

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

Ключові терміни

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

Ключ пошуку - це поле записи, за значенням якого відбувається пошук

Пошук - це процес знаходження конкретної інформації в раніше створеному безлічі даних.

Пошук з бар'єром - це модифікація алгоритму послідовного пошуку, що прискорює процес шляхом визначення граничного елемента.

Послідовний (лінійний) пошук - це найпростіший вид пошуку заданого елемента на деякій множині, здійснюваний шляхом послідовного порівняння чергового розглянутого значення з шуканим до тих пір, поки ці значення не співпадуть.

короткі підсумки

  1. Одним з найважливіших дій зі структурованою інформацією є пошук.
  2. Існує безліч різних алгоритмів пошуку, які принципово залежать від способу організації даних. У кожного алгоритму пошуку є свої переваги і недоліки.
  3. Послідовний (лінійний) пошук є найпростішим видом пошуку заданого елемента на деякій множині, здійснюваним шляхом послідовного порівняння чергового розглянутого значення з шуканим до тих пір, поки ці значення не співпадуть.
  4. Існує модифікація алгоритму послідовного пошуку, яка прискорює пошук шляхом установки в розглянутому безлічі бар'єру.
  5. Бінарний (двійковий, дихотомический) пошук є пошуком заданого елемента на впорядкованій множині, здійснюваним шляхом кількаразового ділення цієї множини на дві частини таким чином, що шуканий елемент потрапляє в одну з цих частин. Бінарний пошук застосовується до відсортованим безлічам.
  6. Перевагою бінарного пошуку є більш низька трудомісткість в порівнянні з послідовним пошуком. Недолік бінарного пошуку полягає в тому, що він застосовується лише на відсортованих множинах.

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?

Уважаемые партнеры, если Вас заинтересовала наша продукция, мы готовы с Вами сотрудничать. Вам необходимо заполнить эту форму и отправить нам. Наши менеджеры в оперативном режиме обработают Вашу заявку, свяжутся с Вами и ответят на все интересующее Вас вопросы.

Или позвоните нам по телефонам: (048) 823-25-64

Организация (обязательно) *

Адрес доставки

Объем

Как с вами связаться:

Имя

Телефон (обязательно) *

Мобильный телефон

Ваш E-Mail

Дополнительная информация: