Интерполяционный поиск - Salmontheturtle/AlevelHW GitHub Wiki

1. Общая информация об интерполяционном поиске.

В основе алгоритма лежит интерполяция (т.е. "нахождение неизвестных промежуточных значений некоторой функции, по имеющемуся дискретному набору её известных значений") зависимости элемента последовательности от значения его индекса. Полученная интерполяционная зависимость используется в качестве возможности предсказания местоположения элемента. Представленный алгоритм, равно как и бинарный поиск, уменьшает область поиска с каждым шагом, но, в отличии от последнего сужает область не в два раза, а несколько быстрее, в зависимости от того, насколько хорошо подобрана поледовательность, поэтому для максимальной эффективности стоит использовать уже отсортированные объекты. В то же время стоит учитывать, что плохо подобранная интерполирующая зависимость может служить причиной падения эффективности до линейной.

Интерполяция графически

Рассмотрим визуализацию интерполяционной функции:

График интерполяционной функции

Где xᵢ и yᵢ – точки данных, базовые точки, при i = 1...N

xᵢ – узлы интерполяции

△x = xᵢ-xᵢ₋₁ – шаг интерполяционной сетки

F – интерполирующая функция

задача интерполяции состоит в нахождении функции F = (xᵢ) = yᵢ

2. Использование данной функции практически в Java.

Но как же применить "интерполярку" на практике в Java? – Ответ довольно прост:

Используя линейную интерполяционную функцию, как самую простую и частоиспользуемую, можем составить следующее уравнение:

(x-x₁)/(x₁-x₂) = (y-y₁)/(y₁-y₂)

Отсюда можно получить, что

(x-x₁)/(x₁-x₂) = (y-y₁)/(y₁-y₂) ⇒ (x-x₁)(y₁-y₂) = (y-y₁)(x₁-x₂)

Используя полученное выражение можем вывести обратную зависимость:

(x-x₁)(y₁-y₂) = (y-y₁)(x₁-x₂) ⇒ y(x) = ((x-x₁)*(y₁-y₂)/x₁-x₂)+y₁

(x-x₁)(y₁-y₂) = (y-y₁)(x₁-x₂) ⇒ y(x) = ((y-y₁)*(x₁-x₂)/y₁-y₂)+x₁

Как же применить уравнение прямой в поиске нашей последовательности? Ведь в последовательности нет никаких координат, x-ов и y-ов.

Берём любую индексируемую, заранее отсортированную последовательность и рассматриваем индекс элемента как x координату, а его значение – как y.

Используя формулу обратной зависимости построим формулу поиска индекса искомого элемента:

i(K)=(((K-K[l])*(l-r))/(K[l]-K[r]))+l

Где i – индекс в последовательности, K[i] – значение элемента по этому индексу, а l и r – две крайние точки по которым строится наша координатная прямая

Иными словами мы выполняем следующие шаги (при учёте, что наша последовательность уже отсортированна):

  1. Берём за крайние точки (l и r) первый и последний элементы последовательности соответственно.

  2. Определяем значение индекса по нашей формуле линейной интерполяции. Получаем элемент по этому индексу. Сравниваем его с искомым. Тут возможны варианты развития событий:

  • а) Элементы равны. Заканчиваем поиск.
  • b) Элемент больше искомого. Сдвигаем правую точку. Новое значение (найденный индекс -1).
  • c) Элемент меньше искомого. Сдвигаем левую точку. Новое значение (найденный индекс +1)

`

public static void main(String[] args) {
	// TODO Auto-generated method stub
	int[] sequince = new int[] { -2, 0, 3, 5, 7, 9, 11, 15, 18 };
	int element = 5;
	System.out.println(interpolationSearch(sequince, element));

}

public static int interpolationSearch(int[] sequince, int element) {
	int l = 0;
	int r = sequince.length - 1;
	for (; sequince[l] < element && element < sequince[r];) {
		if (sequince[l] == sequince[r]) {
			break;
		}
		int index = (element - sequince[l]) * (l - r) / (sequince[l] - sequince[r]) + l;
		if (sequince[index] > element) {
			r = index - 1;
		} else if (sequince[index] < element) {
			l = index + 1;
		} else {
			return index;
		}
	}
	if (sequince[l] == element) {
		return l;
	}
	if (sequince[r] == element) {
		return r;
	}
	return -1;
}

`

3. Алгоритмическая сложность

В случае интерполяционного поиска получается довольно интересная ситуация, так как его О-нотация может быть как линейной (O(n)), так и логарифмической (О(log n)). Линейной его асимптотическая сложность будет в случае неравномерного(например, экспоненциального) возрастания, при условии, что мы взяли линейную функцию в качестве интерполирующей.

В случае же равномерного распределения данных в последовательности, интерполяционный поиск заметно уходит вперёд по сравнению, например, со своим бинарным собратом, за счёт более быстрого сужения области поиска.

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