Однородный бинарный поиск

Else

Else

End

Begin

Begin

Else

End

Begin

Repeat

Begin

Var

Интерполяционный поиск

Метод золотого сечения

 

При поиске методом золотого сечения аргумент поиска А сравнивает-

ся с ключом Ki, где i является золотым сечением интервала поиска. Сущ-

ность золотого сечения заключается в том, что если на плоскости имеет-

ся отрезок длиной а, то золотое сечение делит его на два отрезка соответственно длиной b и с так, что а/b = b/с.

Для уменьшения временных затрат при реализации вычисления золото-

го сечения используют константу, на которую надо разделить интервал а,

чтобы найти его золотое сечение. Эта константа равна

а/b = b/с = 1.619031... .

Алгоритм поиска методом золотого сечения аналогичен алгоритму би-

нарного поиска(рис.3). Отличие состоит только в шаге вычисления номе-

ра I сравниваемого элемента, который в данном случае принимает вид:

I=|_(P-Q)/1,619031 _|+Q.

 

массиве ключей: 20 25 29 32 37 38 39 51 53 57 61 99.

Q=1,P=12,i=7,Ki=39: [20 25 29 32 37 38

Q=8,P=12,i=10,Ki=57: 20 25 29 32 37 38 39[51 53

Q=8,P=9,i=8,Ki=51: 20 25 29 32 37 38 39[

Поиск заканчивается удачно, ключ 51 имеет элемент с номером 8.

Второй пример на заставке. Проверить Р=4, Q=3

 

 

Отличие интерполяционного поиска от предыдущих методов

заключается в том, что выбор очередного ключа Ki для сравнения с аргу-

ментом А зависит не только от Q и P, но и от значений ключей KQ и Kp в

нижней и верхней границах интервала поиска. Если аргумент поиска А на

очередном шаге лежит между KQ и KP, то ключ Ki выбирается на расстоянии

(P-Q)(A-KQ)/(KP-KQ) от Q.

Алгоритм интерполяционного поиска также аналогичен алгоритму би-

нарного поиска. Отличие состоит только в шаге вычисления номе-

ра I сравниваемого элемента, который в данном случае имеет вид:

I = |_ (P-Q)(A-KQ)/(KP-KQ) _| + Q.

Пример. Осуществить интерполяционный поиск аргумента 51 в массиве

ключей: 20 25 29 32 37 38 39 51 53 57 61 99.

Q=1,KQ=20,P=12,KP=99,i=5,Ki=37: [20 25 29 32

Q=6,KQ=38,P=12,KP=99,i=8,Ki=51: 20 25 29 32 37[38 39

Поиск закончен удачно.

 

Q,P,I,FLAG,A,KP,KQ:integer;

KP:=date[N];

KQ:=date[1];

FLAG:=0;

P:=N;

Q:=1;

if P<Q then

FLAG:=1;

Writeln('Объект не найден');

I:=Trunc((P-Q)*(A-KQ)/(KP-KQ))+Q ; (меньшее или равное Х, если Х >=0, и большее или равное Х, если X<0)

if A=date[I] then

FLAG:=1;

Writeln('Объект успешно найден ' + I)

if A>date[I] then

Q:=I+1

P:=I-1;

end;

until FLAG=1;

end;

Всего положительных элементов N, date[0]=0.

 

Недостатки.

1.Нужно вычислять Kp и KQ, что особенно неудобно для файла.

2. Можно применять только для числовых уключей

 

 

При однородном бинарном поиске аргумент поиска А сравнивается с

ключом Ki, находящимся в середине интервала поиска. Отличие этого ме-

тода от бинарного поиска заключается в том, что вместо трех указате-

лей Q, i и P используются только два: текущее положение i и величина

его изменения H. После каждого сравнения A и Ki, не давшего равенства,

устанавливается

I=I+-; H=

Поиск заканчивается неудачно, если приращение становится равным 0.

Структурограмма алгоритма однородного бинарного поиска приведена

на рис.