ЯК реалізувати пошук :: ПЗ

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

Інструкція

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

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

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

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