Căutarea prin interpolare

Aspecte teoretice:

Căutarea prin interpolare este o ameliorare a metodei căutării binare, care se bazează pe strategia adoptată de o persoană când caută un cuvânt într-un dicționar. Astfel, dacă cuvântul căutat începe cu litera C, deschidem dicționarul undeva mai la început, iar când cuvântul începe cu litera V, deschidem dicționarul mai pe la sfârșit. Dacă e este valoarea căutată în vectorul a[ic..sf], atunci partiționăm spațiul de căutare pe poziția m=ic+(e-a[ic])*(sf-ic)/(a[sf]-a[ic]). Această partiționare permite o estimare mai bună în cazul în care elementele lui a sunt numere distribuite uniform.

Cod Sursa C++

// CautareInterpolareCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
/* Cautare prin interpolare */
 
typedef int vector[20];
void Citeste(vector x, int *n)
{
	int p;
	printf("Dati nr. de elemente: "); 
	//scanf("%d", &p);
	cin >> p;
	*n = p;
	cout << "dati " << p << " elemente (in ordine crescatoare).\n";
	for (int i = 0; i<p; i++)
	{
		printf("Dati x[%d]=", i + 1);
		// consideram indexarea de la 1 la n !
		//scanf("%d", &x[i]);
		cin >> x[i];
	}
}
void Afiseaza(vector x, int n)
{
	printf("Elementele lui x sunt: ");
	for (int i = 0; i<n; i++)
		printf("%d,", x[i]);
	printf("%c.\n\n", 8);
}
int CautInterp(vector a, int e, int ic, int sf)
{
	if (ic <= sf)
	{
		int m; m = ic + (e - a[ic])*(sf - ic) / (a[sf] - a[ic]);
		if (e == a[m])
			return m + 1; // atentie la indici !
		else
		if (e<a[m])
			return CautInterp(a, e, ic, m - 1);
		else
			return CautInterp(a, e, m + 1, sf);
	}
	else return 0;
}
void main()
{
	int n, p, e; vector a;
	Citeste(a, &n); 
	Afiseaza(a, n);
	printf("Dati numarul cautat: "); 
	//scanf("%d", &e);
	cin >> e;
	printf("\n");
	if (p = CautInterp(a, e, 0, n - 1))
		printf("%d exista pe pozitia %d in sir !", e, p);
	else printf("%d nu exista in sir !", e);
	system("Pause");
}

Rezultat: