İnterpolyasiya ilə axtarış

İnterpolyasiya ilə axtarış (ing. Interpolation search) — Artan və ya azalan sıra ilə düzülmüş massivdə verilmiş elementin tapılması alqoritmidir.

İşləmə prinsipi

Eyni ilə ikili axtarış alqoritminin sxemi üzrə qurulur. Yeganə fərq ondan ibarətdir ki, massiv hər addımda ikiyə tən ortadan deyil, cari intervalın uclarındakı qiymətlərdən asılı olaraq xətti interpolyasiya ilə tapılmış mövqedən bölünür. Hesablamaya sərf olunan vaxt baxımından intervalın ikiyə ortadan bölunməsi ilə interpolyasıyanın hesablanması arasında fərq ciddi olmadığı üçün, bu intervalın daha böyük sürətlə yığılmasına gətirir. Massivdəki elementlərin sayı N olarsa, bir elementin mövqeyinin tapılması üçün orta hesabla $log(log(N))$ müqayisə sərf edilər. Ən pis halda (məsələn verilənlər eksponsional xarakter daşıdıqda) tələb edilən əməliyatların sayı $O(N)$ -ə çata bilər.

C++ proqramlaşdırma dilində icrasına nümunə

#include <iostream>
#include <stdlib.h>		/*	srand(), rand(), RAND_MAX	*/
#include <time.h>		/*	time()						*/
#include <locale.h>		/*	setlocale()					*/

using namespace std;

const int n = 12;			/* Massivin ölçüsü */

/* Artan sıra ilə düzülmüş massivdə interpolyasiya ilə axtarış funksiyasına nümunə */
int InterpolyasiyaIleAkhtar(int massiv[], int say, int axtarilan)
{
	int sol = 0;
	int sag = say - 1;

	while ((massiv[sag] != massiv[sol]) && (axtarilan >= massiv[sol]) && (axtarilan <= massiv[sag]))
	{
		int yeniMovqe = sol + ((axtarilan - massiv[sol]) * (sag - sol) / (massiv[sag] - massiv[sol]));

		if (massiv[yeniMovqe] == axtarilan)
			return yeniMovqe;

		if (massiv[yeniMovqe] < axtarilan)
			sol = yeniMovqe + 1;
		else
			sag = yeniMovqe - 1;
	}

	if (axtarilan == massiv[sol])
		return sol;

	return -1;
}

/* Massivi sıralamaq üçün tələb olunan müqaisə funksiyası.	*/
/* Bu funksiya massivi artan sıra ilə düzür.				*/
int compare(const void* elem1, const void* elem2)
{
	if (*((int*)elem1) > *((int*)elem2))
		return 1;

	if (*((int*)elem1) < *((int*)elem2))
		return -1;

	return 0;
}

/* Alqoritminin istifadəsinə nümunə */
int main()
{
	int massiv[n];
	int i;

	setlocale(LC_ALL, ".utf8");
	srand((unsigned)time(NULL));

	cout << "Massivdəki ədədlərin ilkin təsadüfi sırası:\t";
	for (i = 0; i < n; i++)
	{
		massiv[i] = 100.0 * rand() / (RAND_MAX + 1);
		cout << massiv[i] << " ";
	}
	cout << endl;

	/* Alqoritm ancaq sıralanmış massivlərlə işləyir */
	qsort(massiv, n, sizeof(int), compare);

	cout << "Massivdəki ədədlər sıralandıqdan sonra:\t\t";
	for (i = 0; i < n; i++)
		cout << massiv[i] << " ";
	cout << endl;

	while (true)
	{
		int axtarilan;

		cout << endl << "Proqramdan çıxmaq üçün mənfi, sırasının tapilması üçün isə hər hansı bir digər ədəd daxil edin: ";
		cin >> axtarilan;

		if (axtarilan < 0)
			break;

		int cavab = InterpolyasiyaIleAkhtar(massiv, n, axtarilan);

		if (cavab < 0)
			cout << "Cavab tapilmadi." << endl;
		else
			cout << "Sıra N=: " << cavab + 1 << endl;
	}
}

Həmçinin bax

Axtarış alqoritmləri