Interpolation search

- INTERPOLATION SEARCH -

 Proses pencarian interpolasi (interpolation search) hampir sama dengan proses pencarian dbinary search, dimana pencarian juga dilakukan pada kumpulan data yang sudah urut. Akan tetapi jika pada binary search data dibagi menjadi dua bagian tiap prosesnya. Contoh pencarian dengan metode ini misalnya pencarian nomer telpon pada daftar phonebook. Misalnya nama data yang dicari berawalan huruf R, maka pencariannya tidak akan dilakukan dari awal, namun langsung membuka 2/3 atau 3/4 dari tebal buku.Jadi, data yang dicari relatif terhadap jumlah data.
Secara umum jika dirumuskan, posisi kunci pencarian interpolasi relatif ini adalah:

– Jika data[posisi] > data yg dicari, high = pos – 1
– Jika data[posisi] < data yg dicari, high = pos + 1
Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu yang
dilakukan dengan perkiraan letak data.

Algoritma interpolation sort

1. Masukan jumlah data
2. input data
3. awal = 0
4. akhir = n-1
5. data yang ingin dicari?
6. posisi = ((cari_data - data[awal])*(akhir-awal)+awal)/(data[akhir]-data[awal])
   cari_data == data[posisi]
7. Jika sama,cetak "data x pada posisi indeks ke-x dan proses pencarian sebanyak x
8. Jika tidak, Bandingkan : jika (data[posisi] < cari_data) awal = pos + 1
9. lakukan langkah 4 dan 5
10. Jika data[posisi] > cari_data, high = pos - 1 maka cetak "tidak ditemukan".

CONTOH FLOWCHART

CONTOH PROGRAM

#include <iostream>
#include <conio.h>
#include <iomanip>

using namespace std;

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

cout<<" I N T E R P O L A T I O N \n";
cout<<"       S E A R C H     \n";
cout<<"==============================\n";
cout<<"Masukan jumlah data : ";
cin>>x;
cout<<"input data :"<<endl;
for (int i=0;i<x;i++)
{
    cin>>data[i];
}
 cout<<"Data: ";
 for(int i = 0; i<x; i++)
 cout<<setw(3)<<data[i];
 cout<<endl<<endl;

 cout << "Data yang dicari : ";
 cin >> cari_data;

    awal = 0;
    akhir = x-1;
    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 indeks 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;
}

OUTPUT

Selamat Mencoba '-')/