Поиск
Поиск является одной из основных операций при обработке информации в ЭВМ. Ее назначение - по заданному аргументу найти среди массива данных те данные, которые соответствуют этому аргументу.
Набор данных (любых) будем называть таблицей или файлом. Любое данное (или элемент структуры) отличается каким-то признаком от других данных. Этот признак называется ключом. Ключ может быть уникальным, т. е. в таблице существует только одно данное с этим ключом. Такой уникальный ключ называется первичным. Вторичный ключ в одной таблице может повторяться, но по нему тоже можно организовать поиск. Ключи данных могут быть собраны в одном месте (в другой таблице) или представлять собой запись, в которой одно из полей - это ключ. Ключи, которые выделены из таблицы данных и организованы в свой файл, называются внешними ключами. Если ключ находится в записи, то он называется внутренним.
Поиском по заданному аргументу называется алгоритм, определяющий соответствие ключа с заданным аргументом. Результатом работы алгоритма поиска может быть нахождение этого данного или отсутствие его в таблице. В случае отсутствия данного возможны две операции:
1. индикация того, что данного нет
2. вставка данного в таблицу.
Пусть k - массив ключей. Для каждого k(i) существует r(i) - данное. Key - аргумент поиска. Ему соответствует информационная запись rec. В зависимости от того, какова структура данных в таблице, различают несколько видов поиска.
