Как реализовать поиск

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

Инструкция

1. Самый простой способ поиска известного элемента в массиве данных – это прямой перебор его значений. Данный алгоритм оптимален для небольших объемов информации. Суть его заключается в прохождении по известной последовательности данных (массиву) и сравнивание каждого элемента с искомым значением. При обнаружении совпадения в зависимости от заданных критериев поиск может быть завершен либо продолжен до конца массива.
2. Однако несмотря на простоту реализации данного метода, его использование нежелательно в массивах, содержащих большие объемы информации, так как при этом значительно повышается ресурсоемкость алгоритма. Для оптимальности поиска в этом случае лучше выполнить предварительную сортировку значений в массиве и реализовать алгоритмы поиска: по бинарному дереву, по дереву Фибоначчи, методом экстраполяций.
3. При работе с упорядоченным массивом используйте более эффективный алгоритм – метод бинарного поиска. Его суть заключается в том, что в процессе перебора границы промежутка приближаются друг к другу, таким образом сужая область поиска. Сравните искомое значение со средним по номеру элементом массива. При совпадении образца с элементом задача считается решенной. Если искомое больше среднего элемента, значит, дальнейший поиск необходимо проводить в части массива, расположенной правее среднего элемента (от начала массива до среднего элемента-1). Если искомое меньше среднего элемента, значит, поиск продолжается в части массива от среднего до последнего элемента. Определив новую область для поиска, описанный алгоритм повторяется, определяя совпадения или сужая область обработки. Данная схема верна для массива, упорядоченного по убыванию.
4. Частные задачи поиска минимального или максимального элемента в заданной последовательности решаются путем назначения начального элемента в качестве искомого. Далее проводится последовательный перебор остальных значений массива: второго с первым, третьего с первым и т.д. При сравнивании взятого за эталон значения выясняется, есть ли в массиве элемент более соответствующий поставленному условию (минимум или максимум). При нахождении такового, за эталон принимается уже он, а перебор продолжается с текущей позиции до конца массива. В результате минимальным (или максимальным) значением в данной группе признается тот элемент, который последним был признан за эталон.