Теория экономических информационных систем


Теория экономических информационных систем - стр. 62


д. до тех пор, пока q не станет больше ключа очередной записи.

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

Значение q последовательно сравнивается с рядом величин р(1), р(1+d1), р(1+2*d1), ..., р(1+k*d1) до тех пор, пока будет впервые достигнуто неравенство р(1+m*d1) =>q. Здесь заканчивается первая ступень поиска. На второй ступени q последовательно сравнивается со всеми ключами, которые имеют номер 1+m*d1 и больше, до тех пор, пока в процессе сравнений будет достигнут ключ, больший, чем q. Извлеченные при этом записи с ключом q образуют результат поиска.

Эффективность поиска измеряется количеством произведенных сравнений.

Важным вариантом ступенчатого поиска является бинарный поиск. Для бинарного поиска вводятся левая граница интервала поиска А и правая граница В. Первоначально интервал охватывает весь массив, т. е. А=0, В=М+1. Вычисляется середина интервала i по формуле i=(А+В)/2 с округлением в меньшую сторону. Ключ i-й записи р(i) сравнивается с искомым значением q. Если р(i) = q, то поиск заканчивается. В случае р(i)>q записи с номерами i+1, i+2,..., М заведомо не содержат ключа, и надо сократить интервал поиска, приняв В=i. Аналогично при р(i) < q надо взять А=i. Далее середина интервала вычисляется заново, и все действия повторяются. Если будет достигнут нулевой интервал, то требуемой записи в массиве нет.

Корректировка последовательного массива

Корректировка массива может касаться одной его записи или группы записей. Отдельная запись может включаться в массив и исключаться из него. Кроме того, в записи могут быть изменены значения отдельных атрибутов (как правило, неключевых). В любом случае перед непосредственно корректировкой выполняется поиск местонахождения корректируемой записи.

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


Начало  Назад  Вперед



Книжный магазин