17.2. Алгоритм дихотомического поиска

Этот алгоритм является более быстрым, чем линейный, но применяется только к упорядоченным массивам. Среднее время дихотомического поиска пропорционально величине log₂n, где n — количество элементов таблицы эталонов.

Метод основан на последовательном делении на 2 диапазона поиска. При этом на каждом шаге либо находится элемент, либо происходит переход в одну из половин диапазона. В процессе поиска выполняется не только сравнение на равенство, но и на больше-меньше. Последняя операция позволяет выбрать очередную половину диапазона таблицы. Если массив эталонов не упорядочен, то выбор будет сделан неверно, и результат можно не получить никогда (говорят, что алгоритм расходится).

Общий алгоритм поиска будет таким же, как в п. 18.1, т.е.

1. Ввести два исходных массива слов (таблицу-словарь).

2. Повторять

ввести новое слово и вывести русское

пока не надоест.

3. Закончить.

Для корректности работы алгоритма необходимо упорядочить словарь (массивы слов) по алфавиту. Эта операция выполняется применительно к основному массиву, используемому при поиске — к английским словам.

Уточненный алгоритм можно представить в следующем виде.

1. Ввести количество слов в словаре (n).

2. Для номера слова (i) от 1 до n выполнить

1.2.1. Ввести Английское_Слово[i].

1.2.2. Ввести Русское_Слово[i].

2. Упорядочить слова по алфивату:

Для номера просмотра (k) от 1 до n - 1 выполнить

Для номера слова (i) от 1 до n - k выполнить

Если Английское_Слово[i] > Английское_Слово[i+1] то

а) поменять местами Английское_Слово[i] и Английское_Слово[i+1];

б) поменять местами Русское _Слово[i] и Русское _Слово[i+1].

3. Повторять

3.2.1. Ввести Слово (для перевода);

3.2.2. Граница_левая (диапазона поиска):= 1;

3.2.3. Граница_правая (диапазона поиска):= n;

3.2.4. Признак:= "Не найдено".

3.2.5. Повторять

а) Номер Русского_Слова (k):= (Граница_левая + Граница_правая)/2;

б) Если Слово = Английское_Слово[i] ТО

Признак:= "Найдено"

Иначе

Если Слово > Английское_Слово[i] ТО

k:= Граница_левая

Иначе

k:= Граница_правая.

Пока не будет "Найдено" Или (Граница_левая = Граница_правая - 1).

3.2.6. Если "Найдено" 0 ТО

вывести Русское_Слово[k]

Иначе

вывести: 'Введенного слова нет в словаре'.

пока не будет Слово = 'End'.

4. Закончить.

Программа дихотомического поиска, соответствующая этому алгоритму, будет иметь вид.

Program DixPoisk;

Const

Nmax = 100;

dl = 15; { длина слова }

Var

Rsl, Asl : Array[1..Nmax] of string[dl];

Slovo : String[dl];

i, k, n: Integer;

Lev, Prav: Integer; { границы }

Naideno: Boolean; { признак }

Begin

Writeln('Введите количество слов');

ReadLn(n);

Writeln('Введите словарь');

For i := 1 to n do

Begin

ReadLn(Rsl[i]);

ReadLn(Asl[i]);

End;

{ Упорядочение словаря по английскому алфавиту }

For k:=1 to n-1 do

For i:=1 to n-k do

If Asl[i] > Asl[i+1] then

Begin

Slovo:= Asl[i];

Asl[i]:= Asl[i+1];

Asl[i]:= Slovo;

Slovo:= Rsl[i];

Rsl[i]:= Rsl[i+1];

Rsl[i]:= Slovo;

End;

{ Перевод }

Repeat

WriteLn('Введите слово для перевода');

ReadLn(Slovo);

Lev:= 1;

Prav:= n;

Naideno:= False; { не найдено }

Repeat

k:=Round(Lev + Prav) / 2);

If Slovo = Asl[k] then

Naideno:= True { не найдено }

Else

If Slovo > Asl[k] then

k:=Lev

Else

k:= Prav;

Until Naideno Or (lev=Prav-1);

If Naideno then

Writeln(Rsl[k])

Else

Writeln('Нет такого слова в словаре');

Until Slovo='End';

Writeln('Работа окончена. Нажмите клавишу ENTER');

Readln;

END.