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

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

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

ся с ключом 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

Лине́йная интерполя́ция — интерполяция алгебраическим двучленом P₁(x) = ax + b функции f, заданной в двух точках x₀ и x₁ отрезка [a, b].

Геометрически это означает замену графика функции f прямой, проходящей через точки (x ₀, f (x ₀)) и (x ₁, f (x ₁)).

Уравнение такой прямой имеет вид:

отсюда для

Это и есть формула линейной интерполяции

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

заключается в том, что выбор очередного ключа 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

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