Все реально применяемые методы поиска относятся к отсортированным таблицам. Для упорядоченной таблицы наиболее эффективными являются: 1) индексно-последовательный поиск и 2) бинарный поиск .
Индексно-последовательный поиск.В дополнение к отсортированной таблице заводится вспомогательная таблица, называемая индексной [9, 11]. Каждый элемент индексной таблицы состоит из ключа и указателя на запись в основной таблице, соответствующую этому ключу kindex. Элементы в индексной таблице, так же как элементы в основной таблице, должны быть отсортированы по этому ключу. Если индекс имеет размер, составляющий одну восьмую от размера основной таблицы, то каждая восьмая запись основной таблицы будет представлена в индексной таблице (рис. 3.1).
Алгоритм индексно-последовательного поиска прост. Предположим, что к — массив из п ключей; г — массив записей такой, что k(i) является ключом для записи r(i); key — аргумент поиска. Пусть — массив ключей в индексе; pindex — массив указателей в индексе на записи. Размер основной таблицы — п. Размер индексной таблицы — indsize.