3.3. Неупорядоченная таблица или метод линейного списка

Наиболее простой метод поиска состоит в том, что входное слово сопоставляется с каждым элементом хранимым в памяти массива или списка слов, до тех пор, пока не происходит совпадение (если оно возможно). Добавляются же элементы к текущему концу заполненной части массива или к последнему элементу в списке. У этого метода есть лишь один недостаток: поиск по длинной таблице займет много времени! Если в таблице N элементов, то ожидаемое число сопоставлений, необходимых для обнаружения случайно выбранного элемента, равно (N+1)/2.

3.4. Упорядоченная таблица. Бинарный, двоичный или логарифмический поиск

Время поиска по таблице большого объема можно значительно сократить, если элементы таблицы упорядочены по аргументу, например, лексикографически, т.е. по алфавиту. Эффективным методом поиска в таком списке является бинарный (двоичный, логарифмический) поиск. Имя S, которое следует найти, сравнивается с аргументом элемента с номером (N+1)/2 в середине таблицы. Если этот элемент не является требуемым, то мы должны просматривать только блок элементов пронумерованных от 1 до (N+1)/2–1 или блок от (N+1)/2+1 до N в зависимости от того, меньше или больше искомый идентификатор S того элемента, с которым его сравнивали. Затем мы повторяем процесс для блока меньшего размера. Так как на каждом шаге число элементов, которые могут содержать S, сокращается наполовину, то максимальное число сравнений –1+log₂N. Если N=2, то необходимо, самое большое, 2 сравнения (N=4, – то 3, N=8, – то 4). Для N=128 потребуется не более 8 сравнений, в то время как среднее время поиска в неупорядоченной таблице того же объема составит 64 сравнения.

Основной недостаток бинарного поиска – необходимость преобразования таблицы при добавлении элементов. Надо не просто добавлять элементы к концу таблицы, а вставлять их туда, где они обязаны находится в соответствии с выбранным порядком, т.е. использовать метод упорядоченных вставок. Он применяется, когда таблица часто просматривается до того, как она полностью заполнена, и, следовательно, должна быть упорядочена на всех этапах. Элемент S вставляется в таблицу следующим образом:

1. Находится k для которого S_k < S < S_k+1.

2. Элемент N сдвигается на позицию N+1, N–1 – на позицию N и т.д. Элемент с номером k+1 сдвигается на позицию k+2.

3. S заносится на место k+1.

Если заполнение таблицы предшествует поискам, то упорядочение проще сделать после заполнения.

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

На рис. 3.3 показано представление таблицы в виде дерева поиска для некоторого подмножества ключевых слов и стандартных типов языка С.

При поиске слова for в этом дереве оно последовательно сравнивается со словами if, do, enum и for.

Разместив дерево в памяти, можно добавлять к нему слова не нарушая этого размещения. Слово bitset, например, присоединится к слову break, а слово delete к слову default. Но, к сожалению, после таких добавлений результирующее время поиска может превышать логарифмическую границу. Для слова delete, например, потребуется 6 сравнений. Если желательно расширить множество слов, сохранив логарифмическое время поиска, необходимо проводить реорганизацию структуры дерева.