Алгоритми пошуку
При роботі з інформацією дуже важливим є пошук. Пошук – процес знаходження у множині даних якоїсь інформації. Зазвичай у даних містяться ключі. Ключ пошуку – це поле запису, використовуючи значення якого, відбувається пошук. Їх використовують щоб розрізняти записи. Загальна мета пошуку – знайти усі збіги записів з певним значенням ключа.
Пошук є однією з найчастіше використовуваних операцій у програмуванні. Взагалі, різноманітних видів пошуку дуже багато і вони розрізняються між собою способом організації даних. Але у кожному алгоритмі пошуку є свої переваги і недоліки.
Загальний алгоритм пошуку можна описати так:
- Обчислення елемента, що часто передбачає отримання значення елемента, ключа елемента і т.д.
- Порівняння елемента з еталоном або порівняння двох елементів.
- Перебір елементів множини, тобто проходження по елементах масиву.
Різняться види пошуку методом перебору і стратегіями пошуку. В лінійних структурах існують такі основні алгоритми.
Послідовний або лінійний пошук
Це самий простий вид пошуку деякого елемента серед інших, що здійснюється за допомогою перевірки кожного елемента до тих пір, поки вони не будуть збігатися. Загальна ідея цього виду пошуку така: усі елементи розглядаються послідовно, один за одним. Це дає змогу не пропустити жодного елемента. Якщо збіг буде знайдено, то пошук припиняється і його результат є позитивним. Якщо не знайдено, то результат буде негативним.
Перевагами такого пошуку є простота його реалізації, він не потребує додаткового об’єму пам’яті або додаткової роботи з функціями. Це дозволяє працювати вже під час отримання даних.
Також існує певний покращений послідовний алгоритм, який пришвидшує пошук. У множині встановлюється бар’єр, тобто елемент, який задовольняє пошуку. У циклі відпадає необхідність перевірки умови, зв’язаної з границями множини. Таким чином буде обмежена зміна індексу.
Бінарний або двійковий пошук
Це такий вид пошуку, у якому пошук елемента з множини відбувається за допомогою ділення деякої кількості раз цієї множини навпіл. Елемент, який треба знайти, колись потрапить або не потрапить в одну з цих двох частин. Бінарний пошук застосовується для відсортованих множин. Ідея цього пошуку така: Пошук даного значення серед деякого масиву починається, коли визначається центральний елемент цього масиву. Значення цього елемента порівнюється зі значенням елемента, який треба знайти. Якщо потрібне нам значення збігається з центральним, то пошук завершено. Якщо воно або більше або менше, то створюється масив, який складається з елементів, що знаходяться ліворуч або праворуч від центрального значення і тепер пошук відбувається в цьому масиві.
Перевагами такого пошуку є швидкість пошуку, якщо порівнювати з послідовним пошуком. Але є й такий недолік, що двійковий пошук може використовуватись лише на упорядкованій множині.
Інтерполяційний пошук
Для цього виду пошуку теж є обмеження: масив повинен бути впорядкований за величиною ключів кожного елемента. У цьому алгоритмі пошуку величини повинні бути рівномірно розподілені у деякому їх інтервалі від x до y. З цього виходить, що якщо є відома величина C ключа пошуку, то положення потрібного нам запису можливо передбачити, а не шукати у всьому файлі. Цей пошук використовується частіше, ніж бінарний.
Отже, алгоритми пошуку дуже різноманітні за своїми типами та способами пошуку. Кожний такий вид заслуговує своє право на існування через свою корисність у певних ситуаціях. Пошук застосовується у всіх мовах програмування, тому його базове знання є важливим.