Последовательный поиск в упорядоченной таблице

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

a[0].Кey < a[1].Кey < ... < a[HighIndex].Кey, (10.3)

а для вторичных ключей условие упорядоченности выглядит как

a[0].Кey £ a[1].Кey £ ... £ a[HighIndex].Кey, (104)

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

ArgSearch £ a[i].Кey для первичных ключей, (10.5)

ArgSearch < a[i].Кeyдля вторичных ключей, (10.6)

где i - индекс первого встретившегося при последовательном просмотре ключа, для которого выполняется одно из приведенных условий.

В случае, когда поиск ведется по первичному ключу, выполнение строгого равенства в (10.5), т. е. когда ArgSearch = a[i].Кey, означает, что поиск завершается с результативным итогом, index = i. Если же выполняется условие ArgSearch < a[i].Кey, то поиск завершается, он неудачен (поскольку a[i+1].Кey, a[i+2].Кey, …, a[HighIndex].Кey заведомо больше ArgSearch), index = -1.

При поиске по вторичному ключу выполнение условия (10.6) приводит к останову алгоритма. Поскольку, согласно (10.4), при этом возможны совпадения аргумента поиска с несколькими значениями ключа (допустим число таких значений равно m), то записи a[i-m], a[i-m+1], …, a[i-1] являются искомыми записями и поиск – результативен. Если же совпадений до выполнения неравенства (10.6) не произошло, то завершившийся поиск неудачен. В любом случае значения a[i+1].Кey, a[i+2].Кey, …, a[HighIndex].Кey не проверяются на совпадение с аргументом ArgSearch, поскольку они заведомо больше ArgSearch .

Таким образом, последовательный поиск в упорядоченной по ключу таблице значительно эффективнее последовательного поиска в неупорядоченной таблице, поскольку при отсутствии в таблице значения (или значений) ключа, совпадающего с аргументом поиска, не следует просматривать все таблицу до конца (если, строго говоря, аргумент не превышает максимального значения ключа).