INTERPOLASI SEARCH

Pencarian Data dengan menggunakan Metode Interpolasi Search

interpolation Search (Pencarian Interpolasi) merupakan proses pencarian yang lebih efisien daripada pencarian Binary dan Sequential Search.Karena apa pada pencarian ini tidak perlu menjelajahi setiap elemen dari tabel, dimana dilakukan pada kumpulan data yang sudah urut. 

Adapun Kerugian :

• Metode ini hanya  bisa digunakan pada tabel yang elemennya sudah terurut baik menaik maupun menurun.
• Teknik ini juga dilakukan pada list yang sudah terurut.

Adapun Keuntungan :

• Lebih ringkas proses pencariannya.

• Metode ini dilakukan pada data yang sudah urut, sehingga akan lebih mudah. 

Rumus Posisi Kunci Pencarian Interpolasi : 

Algoritma Interpolasi Search :

1. Start
2. Banyaknya record array(k)
3. Nilai awal min=0;max=k-1
4. Hitung mid=min+((kunci-k[min])*(max-min))/(k[max]-k[min])
5. Bandingkan data yang dicari(kunci) dengan data posisi tengah(mid)
6. Jika <, proses dilanjutkan dengan posisi max= posisi tengah-1
7. Jika >, proses dilanjutkan dengan posisi min= posisi tengah+1
8. Jika data posisi tengah(mid)= data yang dicari(kunci), maka index= mid,selesai
9. Jika min<=max dan k[mid]=kunci, maka ulang langkah 3
10. Jika k[mid]=kunci, maka index=-1
11. End    

Kode Program Interpolation Search dalam bahasa C++ :

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

int main()
{
       int DATAKU[12] = {7,10,13,20,24,30,41,45,56,76,89,90};
       int cariDATAKU, i, flag = 0;
       int saveindex[12];
       int jum_index=0;

       cout<<"INTERPOLATION SEARCH"<<endl;
       cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;
       cout<<"DATA YANG ADA   : ";
              for(int n= 0; n<12; n++)
                     cout<<setw(4)<<DATAKU[n];
       cout<<endl;
        cout<<"^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^"<<endl;
       cout<<"\nMasukkan data yang ingin Anda cari : ";
       cin>>cariDATAKU;

       for(i = 0; i<12; i++)
        {
              while(DATAKU[i]==cariDATAKU)
              {
                     flag = 1;
                     saveindex[jum_index] = i;
                     jum_index++;
                     break;
              }
       }

       //cetak hasil
       if(flag==1)
       {
              for( int y = 0; y < jum_index; y++ )
              cout<<"Data ditemukan pada index ke-"<<saveindex[y]<<endl;
       }
       else
              cout<<"Data tidak ditemukan"<<endl;

       getche();

}

Hasil Output 1
 

Hasil Output 2