Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19

12. Поиск

Одно из наиболее часто встречающихся в программирова- нии действий — поиск данных. Существует несколько основных

ВіІ]ЭИlІНТОВ ПОИСКІІ, И ДЛЯ НИХ СОЗД tHO МНОГО ]ЭІІЗЛИЧНЫХ ІІЛГО]ЗИТ-
мов. При дальнейшем рассмотрении делается принципиальное допущение: группа данных, в которой необходимо найти задан- ный элемент, фиксирована. Будем считать, что множество из N элементов задано в виде такого массива
var а: array [0..N— 1] of Item

Обычно тип I heт описывает запись с некоторым полем, играю- щим роль ключа. Задача заключается в поиске элемента, ключ которого равен заданному «аргументу поиска» х. Полученный в результате индекс i, удовлетворяющий условию а [ і ] . k eу

х, обеспечивает доступ к другим полям обнаруженного элемента. Так как здесь рассматривается, прежде всего, сам процесс поиска, то мы будем считать, что тип I heт включает только ключ.
С точки зрения теории множеств поиск можно рассматри- вать, как отображение множества Х = ^(x_{i. ›2. .} .гр} на мНОжёСТВО Х' = ^(x_kl! Х' является поДМНожеством Х, и _{•k ——} х _- Если искомых данных в множестве Х нет, то множество Х' является пустым.
Поиск требуемой информации применяется ко всем основ- ным структурам данных с произвольным доступом: массивам, спискам (одно— и двусвязным), деревьям, графам, таблицам.


12.1. Последовательный поиск

Нахождение информации в неотсортированной структуре данных, например в массиве, требует применения последова- тельного поиска.

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

158
cTpyKTypsI pIlHHhIX. Hepe6o]3 aJléMéHTOB HMééT JIHHéJJHhI XI1]3I1KTé]3,

nO3ToMy TaKO noHCK éIIJ HII3I›IBIIIOT JIHHé HI›IM.
PllcGMoTpiiM npnuepsI nOcue@OBI1TéJIsHoro noHCKII C uriKJIIlMH
for while.
&yHKuHii JIHHé JHOFo HOHCKII HH II3hIKé IlCKIlJIh.

var
nums: array [0..N] of real;

function search s1(item: ’real; n: integer;

key: real) :integer; var
i: integer; begin
for i := 0 to N do
if key = item[i] then begin
search s1 := i;
break
end
else
search s1 := -1
end;

function search s2(item: ’real; n: integer; key: real) :integer;

var
i: integer; begin
i:=0;
search s2 := -1;
while (key <> item[i]) or ( i < n) do begin
if key = item[i] then
search s2 := i; i i + 1
end end;
159
Аналогичные процедуры на языке Си++:

int search s1(float* item, int п, float key)

for (int i = 0; i < N; i++) if (key == item[i])

return i; return —1;

int search s2(float* item, int п, float key) int i=0;

while (key != item[i] i < п)

if (key == item[i]) return i;

i++;

return —1;

Последовательный поиск в среднем случае выполнит про- верку N/2 элементов, в лучшем — 1 элемента, а в худшем — N эле- ментов, таким образом, трудоёмкость алгоритма выражается как

Недостаток этого поиска — медленное выполнение при большом объеме просматриваемого массива. Но если данные не отсортированы, то должен использоваться только последователь-

@вопчный (или бинарный) поиск основан на итерационном сравнении ключа поиска с центральным элементом текущей час-

При каждой итерации находится середина текущей анализи- руемой части, т.е. интервал анализа делится пополам (на 2): 1/2, 1/4, 1/8 и т.д., откуда этот метод поиска и получил свое название

160
(ещё один вариант названия — дихотомический). При неудачном сравнении ключа поиска с текущими данными, в зависимости от результата сравнения, выбирается нижний или верхний полуин- тервал. Процесс продолжается до тех пор, пока не будет найдено совпадение или длина интервала анализа не станет равной еди- нице, и если при этом всё ещё нет совпадения, то фиксируется неудача поиска. Процесс поиска числа 40 в упорядоченном мас- сиве целых чисел от 1 до 127 показан на рисунке 12.1.

		63
32		63
32	48	63
32	48

127
Рис. 12.1 Поиск числа 40 при помощи двоичного алгоритма

Этот метод поиска значительно эффективнее чем последо- вательный поиск, но требует, чтобы данные были предварительно упорядочены (отсортированы). В худшем случае выполняется не более

(12.1)

сравнений (где (' 0,0861), в связи с чем двоичный поиск ещё на- зывается "логарифмическим поиском". Трудоёмкость его опре- ^{деляется как P(lo}g2NJ.

Фактически упорядоченный массив используется как дво-
ичное дерево поиска, каждый элемент массива является узлом дерева. Корень дерева — центральный элемент массива. В процес- се поиска выполняется обход дерева в нисходящем порядке. Именно использованием дерева и объясняется высокая эффек- тивность алгоритма.
Функция двоичного поиска на языке Паскаль.

function search_b(item: ’real; п: integer; key: real) :integer;

161
var
low, high, mid: integer; begin
search b := —1; low 0;
high := n — 1;
while low <= high do begin
mid := (low high) / 2; if key < item[mid] then
hig := mid — 1 else
if key > item[mid] then low := mid + 1
else
search b := mid
end
end;

int search b(float* item, int n, float key) int low, high, mid;
low = 0; high= n 1; while (low <= high)

mid = (low + high) / 2;

if (key < item[mid])
high = mid - 1; else
if (key > item[mid]) low = mid + 1;
else return mid; return -1;

Cy ecTByioT MOQnQiixauiiii aarO]3HTMII'

— c pByMs neJ3éMéHHhIMH BMéGTO 1or, h iqh, mi d (HHWHé ,
162
верхней границы и середины интервала анализа) теку- щее положение и величина его изменения. Такой метод требует аккуратности;
алгоритм со вспомогательными таблицами.