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

 

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

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

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

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

2. Повторять

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

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

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

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

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

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

1.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.