Алгоритмы поиска

Предположим, что у нас имеется следующая структура:

struct Ttype {

type key; // Ключевое поле типа type

... // Описание других полей структуры

} * a; // Указатель для динамического массива структур

Задача поиска требуемого элемента в массиве структур a (размер n – задается при выполнении программы) заключается в нахождении индекса i_key, удовлетворяющего условию a [ i_key ]. key = f_key, key – интересующее нас поле структуры данных, f_key – искомое значение того же типа что и key. После нахождения индекса i_key обеспечивается доступ ко всем другим полям найденной структуры a [ i_key ].

Линейный поиск используется, когда нет никакой дополнительной информации о разыскиваемых данных, и представляет собой последовательный перебор всех элементов массива. Если поле поиска является уникальным, то поиск выполняется до обнаружения требуемого ключа или до конца, если ключ не обнаружен. Если же поле поиска не уникальное, приходится перебирать все данные до конца массива:

int i_key = 0, kod = 0;

for (i = 1; i < n; i++)

if (a[i].key == f_key) {

kod = 1;

// Обработка найденного элемента, например, вывод

i_key = i;

// break; – если поле поиска уникальное

}

if(kod == 0) // Вывод сообщения, что элемент не найден

Поиск делением пополам используется, если данные упорядочены по возрастанию (по убыванию) ключа key. Алгоритм поиска осуществляется следующим образом:

– берется средний элемент m;

– если элемент массива a [ m ]. key < f _ key, то все элементы i m исключаются из дальнейшего поиска, иначе – исключаются все элементы с индексами i> m.

Приведем пример, реализующий этот алгоритм

int i_key = 0, j = n–1, m;

while(i_key < j) {

m = (i_key + j)/2;

if (а[m].key < f_key) i_key = m+1;

else j = m;

}

if (a[i_key].key! = key) return -1; // Элемент не найден

else return i;

Проверка совпадения a [ m ]. k = f _ key в этом алгоритме внутри цикла отсутствует, т.к. тестирование показало, что в среднем выигрыш от уменьшения количества проверок превосходит потери от нескольких «лишних» вычислений до выполнения условия i_key = j,