Двоичный способ

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

Рассмотрим вначале, как выполняется просмотр полей элемента.

Пример 5. Пусть требуется просмотреть адрес студента по фамилии Скворцов в списке из таблицы 3, т.е. q^{просмотр} = (Фамилия = Скворцов, Домашний адрес), где К_доступ = Скворцов. Задача решается следующим образом:

1. список виртуально делится пополам: «средним» элементом оказывается элемент, имеющий ключ Соколов;

2. ключ доступа сравнивается с ключевым полем «среднего» элемента: Соколов = Скворцов;

3. поскольку ключи не равны, определяется, в какой из полученных двух половин списка продолжать поиск. Для этого проверяется условие: Соколов < Скворцов;

4. условие выполняется, поэтому поиск продолжается в первой половине, т.е. исходный список уменьшился до размеров таблицы 4:

Таблица 4

5. этот новый список делится на две части: «средним» элементом оказывается элемент, имеющий ключ Скворцов;

6. ключ доступа сравнивается с ключевым полем «среднего» элемента: Скворцов = Скворцов;

7. поскольку условие выполняется, выводится адрес: пр. Мира, 45 – 3; алгоритм заканчивает работу.

Пример 6. Пусть надо просмотреть адрес студента по фамилии Сидоров, т.е. q^{просмотр} = (Фамилия = Сидоров, Домашний адрес), где К_доступ = Сидоров.

Первые пять шагов решения задачи совпадают с предыдущим примером. Затем выполняются следующие шаги:

1. ключ доступа сравнивается с ключевым полем «среднего» элемента: Скворцов = Сидоров;

2. поскольку условие не выполняется, определяется, в какой из полученных двух половин списка продолжать поиск. Для этого проверяется условие: Скворцов > Сидоров;

3. условие выполняется, поэтому делается попытка продолжить поиск в «верхней» части списка. Однако элемент с ключом К_э = Скворцов является единственным элементом в этой части, поэтому выдается диагностическое сообщение об отсутствии искомого элемента в списке; алгоритм заканчивает работу.

Задача добавления нового элемента решается аналогично способу, рассмотренному ранее для упорядоченного списка.