PROGRAM C++ INTERPOLATION SEARCH

Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu. Teknik searching ini dilakukan dengan perkiraan letak data. Contoh ilustrasi: jika kita hendak mencari suatu kata di dalam kamus telepon, misal yang berawalan dengan huruf J, maka  kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada 1/3 atau 1/4 dari tebal kamus.

Rumus posisi relatif kunci pencarian dihitung dengan rumus:

- Jika data[posisi] > data yg dicari, high = pos – 1
- Jika data[posisi] < data yg dicari, low = pos + 1

Berikut contoh Program C++ Interpolation Search

#include
#include
#include

main()
{
int data[8] = {0,1,1,2,3,3,9,9};
int low,high,cari,posisi;
float posisi1;
int N = 8,
tanda=0;
low=0,high=N-1;
cout<<" Datanya yaitu : "<for(int z=0; z<=7; z++)
{
cout<<"\t"<}
cout<<"================================="<cout<<"Masukan data yang di cari = ";cin>>cari;
do                                                        

{
posisi1 = (cari-data[low])/(data[high]-data[low])*(high-low)+low;
posisi = floor(posisi1); //pembulatan ke bawah
if(data[posisi]==cari)
{
tanda =1;
break;
}
if(data[posisi]>cari)
{
high=posisi-1;
}
else if (data[posisi]{
low=posisi+1;
}
}
while (cari>=data[low]&&cari<=data[high]);
if(tanda==1)
{
cout<cout<cout<Data ditemukan <::"<}
else
{
cout<Data tidak ada <::"<}
getch();
}