Основні пошукові алгоритми

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

Крок 1. Обчислення елемента, що часто передбачає отримання значення елемента, ключа елемента і т.д.

Крок 2. Порівняння елемента з еталоном або порівняння двох елементів (в залежності від постановки задачі).

Крок 3. Перебір елементів множини, тобто проходження по елементах масиву.

Основні ідеї різних алгоритмів пошуку зосереджені в методах перебору і стратегії пошуку.

Розглянемо основні алгоритми пошуку в лінійних структурах більш докладно. пошук алгоритм бінарний

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

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

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

Алгоритм послідовного пошуку

Крок 1. Вважаємо, що значення змінної циклу i = 0.

Крок 2. Якщо значення елемента масиву x [i] дорівнює значенню ключа key, то повертаємо значення, рівне номеру шуканого елемента, і алгоритм завершує роботу. В іншому випадку значення змінної циклу збільшується на одиницю i = i +1.

Крок 3. Якщо i <k, де k - число елементів масиву x, то виконується Крок 2, в іншому випадку - робота алгоритму завершена і повертається значення рівне -1.

При наявності в масиві декількох елементів із значенням key даний алгоритм знаходить тільки перший з них (з найменшим індексом).

Sub Main()

Dim arr(30) As Integer

Dim rnd As New Random()

Dim arr_size = 30

Dim key As Integer

Dim i As Integer

key = 5

For i = 0 To arr_size-1

arr(i) = Int(rnd.NextDouble() * 20)

Console.Write("{0} ", arr(i))

Next i

лінійний пошук

For i = 0 To arr_size-1

If (arr(i) = key) Then

Exit For

End If

Next i

If (i > arr_size-1) Then

i = -1

End If

Console.WriteLine()

Console.WriteLine("Result: {0}", i)

End Sub

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

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

Бінарний (двійковий) пошук

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

Бінарний пошук застосовується до відсортованої множини і полягає в послідовному розбитті множини навпіл і пошуку елемента тільки в одній половині на кожній ітерації.

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

Рис.1. Демонстрація алгоритму бінарного пошуку

Алгоритм бінарного пошуку

Крок 1. Визначити номер середнього елемента масиву middle = (high + low) / 2.

Крок 2. Якщо значення середнього елемента масиву дорівнює шуканому, то повертаємо значення, рівне номеру шуканого елемента, і алгоритм завершує роботу.

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

У масиві може зустрічатися декілька елементів зі значеннями, рівними ключу. Даний алгоритм знаходить перший елемент, що співпав з ключем, який в порядку проходження в масиві може бути ні першим, ні останнім серед рівних ключу. Наприклад, в масиві чисел 1, 5, 5, 5, 5, 5, 5, 7, 8 з ключем key = 5 співпаде елемент з порядковим номером 4, який не відноситься ні до першого, ні до останнього.

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

Sub Main()

Dim arr(30) As Integer

Dim rnd As New Random()

Dim arr_size = 30

Dim key As Integer

Dim i As Integer

Dim j As Integer

Dim Tmp As Integer

key = 5

For i = 0 To arr_size-1

arr(i) = Int(rnd.NextDouble() * 20)

Console.Write("{0} ", arr(i))

Next i

'сортування

For i = 0 To arr_size-1

For j = 0 To i

If arr(j) > arr(i) Then

Tmp = arr(j)

arr(j) = arr(i)

arr(i) = Tmp

End If

Next j

Next i

Console.WriteLine()

For i = 0 To arr_size

Console.Write("{0} ", arr(i))

Next i

'бінарний пошук

Dim found = False

Dim high = arr_size-1

Dim low = 0

Dim middle As Integer

middle = (high + low) / 2

While ((found = False) And (high >= low))

If (key = arr(middle)) Then

found = True

ElseIf (key < arr(middle)) Then

high = middle - 1

Else

low = middle + 1

End If

middle = (high + low) / 2

End While

If (found) Then

i = middle

Else

i = -1

End If

Console.WriteLine()

Console.WriteLine("Result: {0}", i)

End Sub

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

Завдання

1. Реалізувати алгоритми лінійного і бінарного пошуків

2. У введеному масиві даних знайти два найменших елементи

3. Вводиться послідовність із N натуральних чисел. Необхідно визначити найменше натуральне число , яке відсутнє у послідовності.

4. На перфострічці записані N попарно різних додатних чисел. Ваша ЕОМ може перемотувати стрічку на початок і зчитувати число одне за одним. Внутрішня пам'ять комп'ютера може зберігати тільки декілька цілих чисел. Необхідно знайти найменше додатне ціле число, якого немає на стрічці. Опишіть алгоритм, який зробить це за найменшу кількість кроків.

5. На столі у двох стовпчиках лежать 64 золотих і 64 срібних монети відповідно. Як срібні, так і золоті монети впорядковані у порядку спадання мас. Маси всіх монет різні. Яку найменшу кількість зважувань необхідно для визначення шістьдесят четвертої монети в порядку убування мас серед всіх 128 монет? За один раз можна зважувати дві монети і визначити, яка з них важче. Відповідь обгрунтувати.

6. Задано N наборів монет з різних країн. Набори впорядковані за неспаданням маси монет. У i-му наборі ai монет. Необхідно за мінімальне число зважувань на вагах визначити к-ту за масою монету серед усіх монет.

Размещено на Allbest.ru