1.2. Поиск.

Одним из наиболее важных и широко распространенных процессов обработки информации является поиск. Задача поиска в информационном массиве (ИМ) состоит из нахождения элемента, который удовлетворяет некоторому заданному условию.

Предположим, что в памяти хранится ИМ из N элементов. Если в качестве элементов выступают записи, тогда имеем файл из N записей. Каждая запись содержит поле ключа, причем все N значений ключей различны, т.е. записи определяются ключом однозначно. В алгоритмах поиска присутствует так называемый аргумент поиска z, который является ключом искомой записи. Задача поиска состоит в отыскании записи, имеющей ключ Z.

Поиск может осуществляться по первичному ключу, который однозначно определяет запись в файле. Но иногда необходимо вести поиск, основываясь не на первичных ключах, а на значениях других полей записи, которые называются атрибутами или вторичными ключами записи. Выборка по вторичным ключам соответствует вторичным методам доступа и допускает одинаковые значения вторичных ключей для нескольких записей, т.е. из файла выбираются записи с одинаковыми значениями атрибутов. Например, из файла СЛУЖАЩИЕ выбираются служащие одного года рождения.

Существует две возможности окончания поиска: поиск удачен, т.е. положение записи, содержащей z, определено, или поиск неудачен, т.е. аргумент z не может быть найден ни в одной из записей.

Классификацию методов поиска можно осуществлять различными способами. Существуют методы поиска, использующие истинные ключи, и методы, использующие преобразованные ключи.

К первой группе следует отнести:

1. Метод последовательного поиска. Элементы ИМ просматриваются последовательно в соответствии с отношением следования, определенном на данном множестве элементов.

2. Метод бинарного поиска. Аргумент поиска (ключ) сравнивается со средним элементом из упорядоченной последовательности. Выделяется один интервал из двух, в котором должен содержаться искомый элемент. Для выбранного интервала изложенный способ повторяется.

Ко второй группе следует отнести:

1. .Метод позиционной адресации, основанный на непосредственной выборке по номеру, определяемому функцией преобразования ключей. Эта функция реализует взаимооднозначное соответствие 1:1 между множеством ключей и множеством адресов записей.

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

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

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

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