Pencarian Interpolasi

Algoritma Pencarian Interpolasi

1.  Mulai.

2.  Menentukan index dan isi dari index tersebut .

0	1	2	3	4	5	index
20	25	30	35	40	45	value

3.  Menentukan keyword yang akan dicari.

     Keyword = 40

     Keyword = 23

4.  Memasukkanya pada rumus Interpolasi.

(40 – 20)

Posisi = 0 + ------------  x(5 – 0) = 4

      (45 – 20)

                                                       (23 – 20)

                           Posisi = 0 + ------------ x(5 – 0) = 0,6 dibulatkan = 1

      (45 – 20)

5.   Jika hasilnya benar sesuai dengan perhitungan menggunakan rumus interpolasi maka pencarian akan berhenti karena keyword telah ditemukan tetapi jika hasil berbeda dengan posisi yang ada pada rumus maka data tersebut tidak ditemukan pada data yang ada.

     Posisi atau index ke 4 memiliki value 40, berarti keyword yang di cari di temukan di index    ke – 4 yang terdapat dalam data.

     Posisi atau index ke 1 memiliki value 25 sedangkan keyword yang di cari adalah 23 maka, keyword 23 tidak terdapat dalam data yang ada.

6. Tampilkan Data

7. Selesai.

Flowchart

 

Script Program Interpolation Sort

#include <iostream>
#include <conio.h>
#include <iomanip>
using namespace std;

int main ()
{
int data[100];
int cari_data, posisi, awal, akhir, proses,x[100],n;
bool berhenti = false;

cout<<"Masukan Jumlah Data : ";
 cin>>n; cout<<endl;
for(int x=0; x<n; x++){
    cout<<"Data ke-"<<x+1<<endl;
cin>>data[x];
}
cout<<"Data awal: ";
for(int x = 0; x<n; x++)
    cout<<setw(3)<<data[x];
    cout<<endl<<endl;
cout<<"Data : ";
for(int x =0; x<n; x++)
cout<<setw(3)<<data[x];
cout<<endl<<endl;
cout<<"Data yang di cari : "; cin>>cari_data;
awal = 0; akhir =x[100]*n; proses = 0;
while(berhenti != true)
{
    proses++;
    posisi=(((cari_data-data[awal])*(akhir-awal))/(data[akhir]-data[awal])+awal);
    if(data[posisi] == cari_data)
    {
        cout<<"Data "<<cari_data<<" Pada posisi indexs ke- "<<posisi<<endl;
        cout<<"Proses pencarian sebanyak : "<< proses<< endl;
        berhenti = true;
    }
    else if(data[posisi]<cari_data){
awal=posisi+1;
} else{
cout<<"Data "<<cari_data<<" tidak ditemukan.\n";
berhenti=true;
}
}
return 0;
}

  

Hasil Program Interpolation Sort