INTERPOLATION SEARCH

INTERPOLATION SEARCH

      Interpolation Search adalah sebuah algoritma atau metode untuk mencari nilai key yang diberikan dalam array diindeks yang telah diperintahkan oleh nilai – nilai kunci.

      Metode ini didasari pada proses pencarian nomor telepon pada buku telepon yang mana manusia mencari melalui dengan nilai kunci yang terdapat pada buku. Teknik searching ini dilakukan dengan perkiraan letak data. Rumus posisi relatif kunci pencarian dihitung dengan rumus berikut ini :

– Jika data[posisi] > data yg dicari, high = pos – 1

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

      Itu saja mengenai Interpolation Search, sekarang saya akan menunjukkan algoritma, script, dan outputnya menggunakan bahasa C++. 

1. Algoritma Interpolation Search :

·                     Mulai

·                     Banyaknya record array (k)

·                     Nilai awal min=0 ; max=k-1

·                     Hitung mid= min + ((kunci - k[min]) * (max - min)) /(k[max] – k[min])

·                     Bandingkan data yang dicari(kunci) dengan data posisi tengah(mid)

·                     Jika lebih kecil, proses dilanjutkan dengan posisi max = posisi tengah-1

·                     Jika lebih besar, proses dilanjutkan dengan posisi min=posisi tengah+1

·                     Jika data posisi tengah(mid) = data yang dicari(kunci) , maka index=mid, selesai

·                     Jika min<=max dan k[mid]=!kunci, maka ulangi langkah 3

·                     Jika k[mid]=!kunci, maka index=-1

·                     selesai 

2. Kode Pemrograman Interpolation Search C++ :

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

int main()
{
       int elemen[10] = {21,54,20,64,41,33,41,78,16,36};
       int carielemen, i, flag = 0;
       int simpanindex[10];
       int jum_index=0;

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

       for(i = 0; i<10; i++)
        {
              while(elemen[i]==carielemen)
              {
                     flag = 1;
                     simpanindex[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-"<<simpanindex[y]<<endl;
       }
       else
              cout<<"Data tidak ditemukan"<<endl;

       getche();

}

3. Berikut adalah output dari kode diatas :