При розробці алгоритмів для вирішення багатьох завдань часто постає проблема реалізації пошуку певної групи даних за заданими критеріями. При дослідженні впорядкованої або неупорядкованої послідовності пошук може здійснюватися за допомогою різних методів. У загальному випадку для вирішення завдання пошуку розглядають певний масив даних, в якому потрібно знайти заданий елемент.
Інструкція
1. Найпростіший спосіб пошуку відомого елемента в масиві даних - це прямий перебір його значень. Цей алгоритм оптимальний для невеликих обсягів інформації. Суть його полягає в проходженні за відомою послідовністю даних (масиву) і порівнювання кожного елемента з шуканим значенням. При виявленні збігу залежно від вказаних критеріїв пошук може бути завершено або продовжено до кінця масиву.
2. Однак незважаючи на простоту реалізації даного методу, його використання небажане в масивах, що містять великі обсяги інформації, оскільки при цьому значно підвищується ресурсоємність алгоритму. Для оптимальності пошуку в цьому випадку краще виконати попереднє сортування значень в масиві і реалізувати алгоритми пошуку: по бінарному дереву, по дереву Фібоначчі, методом екстраполяцій.
3. Під час роботи з впорядкованим масивом використовуйте більш ефективний алгоритм - метод бінарного пошуку. Його суть полягає в тому, що в процесі перебору кордону проміжку наближаються один до одного, таким чином звужена область пошуку. Порівняйте значення з середнім елементом масиву. При збігу зразка з елементом завдання вважається вирішеним. Якщо шукати більше середнього елемента, значить, подальший пошук необхідно проводити в частині масиву, розташованій правіше середнього елемента (від початку масиву до середнього елемента-1). Якщо шукати менше середнього елемента, то пошук триває в частині масиву від середнього до останнього елемента. Визначивши нову область для пошуку, описаний алгоритм повторюється, визначаючи збіги або звуження області обробки. Ця схема правильна для масиву, впорядкованого зі збування.
4. Приватні завдання пошуку мінімального або максимального елемента в заданій послідовності вирішуються шляхом призначення початкового елемента як шуканого. Далі проводиться послідовний перебір інших значень масиву: другого з першим, третього з першим тощо. При порівненні взятого за еталон значення з 'ясовується, чи є в масиві елемент більш відповідний поставленій умові (мінімум або максимум). При знаходженні такого, за еталон приймається вже він, а перебір триває з поточної позиції до кінця масиву. У результаті мінімальним (або максимальним) значенням у даній групі визнається той елемент, який останнім був визнаний за еталон.