Краткие итоги

1. Одним из важнейших действий со структурированной информацией является поиск.

2. Существует множество различных алгоритмов поиска, которые принципиально зависят от способа организации данных. У каждого алгоритма поиска есть свои преимущества и недостатки.

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

4. Существует модификация алгоритма последовательного поиска, которая ускоряет поиск путем установки в рассматриваемом множестве барьера.

5. Бинарный (двоичный, дихотомический) поиск является поиском заданного элемента на упорядоченном множестве, осуществляемым путем неоднократного деления этого множества на две части таким образом, что искомый элемент попадает в одну из этих частей. Бинарный поиск применяется к отсортированным множествам.

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

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

var a: array [0..N–1] of Item

Обычно тип Item описывает запись с некоторым полем, играющим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному «аргументу поиска» x. Полученный в результате индекс i, удовлетворяющий условию а[i].key = x, обеспечивает доступ к другим полям обнаруженного элемента. Так как здесь рассматривается, прежде всего, сам процесс поиска, то мы будем считать, что тип Item включает только ключ.

С точки зрения теории множеств поиск можно рассматривать, как отображение множества X = {x₁, x₂,..., x_N} на множество X' = {x_k}, X' является подмножеством X, и x_k = x_i. Если искомых данных в множестве X нет, то множество X' является пустым.

Поиск требуемой информации применяется ко всем основным структурам данных с произвольным доступом: массивам, спискам (одно- и двусвязным), деревьям, графам, таблицам.