9.1. Поиск. Основные понятия

С задачами поиска информации человеку приходиться сталкиваться постоянно. Типичными примерами служит поиск по справочникам, телефонной книге, картотеке и т.д. Полагаем, что файл  состоит из записей с ключами и пусть K – значение ключа. Различают четыре варианта простейших задач.

1). Требуется определить, по крайней мере, одну запись из -файла, имеющую своим ключом K.

2). Определить все записи из -файла, имеющие K своим ключом.

3). Если в -файле нет записей с ключом K, то добавить новую запись.

4). Включить в -файл новую запись.

K называется аргументом поиска или запросом, первые две задачи простым статическим поиском, а последние две – динамическим поиском со вставкой. Иногда в трех первых задачах поиск организуется не по ключу, а по выполнению некоторых условий для определенной функции от ключей. Примером может служить поиск по интервалу значений ключа, когда отыскиваются записи с условиями: , где a и b – константы. Методы поиска классифицируются по местонахождению и изменению -файла, схеме доступа к отдельным записям , способу сравнения ключей или функций от них и т.п. Например, поиск называется внутренним, если -файл целиком размещается в оперативной памяти, и внешним – в противном случае. Здесь мы будем рассматривать только внутренний поиск. Под файлом будем понимать одномерный или двумерный числовой или символьный массив, и поиск вести в одномерной или двумерной таблице.

Различные варианты задач поиска встречаются при решении других проблем, например, в сортировках, где постоянно приходиться искать пары для текущих обменов. От организации исходной информации во многом зависит эффективность алгоритмов поиска. И в этом контексте сортировки играют полезную роль в предварительном преобразовании -файла. В различных информационных системах поиск требует наибольших временных затрат. Поэтому эффективность их программного обеспечения прямо зависит от типа используемого алгоритма поиска.