6.2. Упорядоченные файлы

Один из простейших методов индексации - хранение информации в файлах в упорядоченном виде по индексируемому полю.
6.2.1. Дихотомический поиск
Этот метод работает следующим образом. Файл делится условно на 2 части и путем сравнения выясняется, в какой части следует искать нужный элемент. Поиск продолжается в нужной части. Далее оставшаяся часть снова делится на две части и т.д.
Запишем алгоритм.
 

f - файл, n - число записей в нем, d - длина записи a:=1; b:=n;

while (b-a)>=0 do begin

c:=(a+b) div 2; //вычисляем номер средней записи k:=(c - 1)*d; //вычисляем смещение «средней записи» seek(f, k); //установка текущей позиции на смещение read(f, r);

if г.^о='Одинцова' then begin return(OK); //задача решена break end;

if ^^о^Одинцова' then b:=c-1 else a:=c+1; // область поиска end;

Примечание. Если возможен прямой доступ, то T~logn (точнее log2 n). Возможность прямого доступа - организуется путем буферизации таблицы во внутренней памяти.
Трудоемкость построения структуры ~nlogn (трудоемкость задачи сортировки последовательности из n элементов - в данном случае сортируются строки таблицы).