Penjelasan 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
Oke, sekian pendahuluan mengenai Interpolation Search, sekarang aku ingin membagi sesuatu yang mungkin bisa bermanfaat buat temen – temen yang sedang ngerjakan tugas untuk Implementasi Interpolation Search dengan C++.
Source code dibawah ini adalah contoh implementasi dari satu fungsi yang aku buat tersendiri di luar fungsi main() yang bernilai int, dan bervalue / nilai yang dihasilkan fungsi ini adalah posisi index array dimana tempat / posisi data yang Anda cari pada suatu array / kumpulan data yang sudah ada.


Pseudocode :
1. Urutkan item-item di dalam array/list
2. Cari item yang berada di tengah
3. Jika indeks batas kiri lebih besar daripada indeks batas kanan, nilai tidak ditemukan, hentikan.
4. Jika item yang di tengah sama dengan nilai yang dicari, hentikan.
5. Jika tidak, ada dua kemungkinan
6. Jika nilai yang dicari lebih kecil dari pada item yang di tengah:
7. Lanjut ke langkah ke 2 untuk bagian array sebelum item yang di tengah
8. Jika nilai yang dicari lebih besar dari pada item yang ditengah:
9. Lanjut ke langkah ke 2 untuk bagian array setelah item yang di tengah

contoh programnya Interpolation Search :

#include<iostream>
#include<conio.h>
#include <ctype.h>
#include <dos.h>
#define n 20
#define PI  3.1415
#define N   12

using namespace std;

int main()
{   static int K[n+1]= {0,10,15,20,25,40,45};
    int kode,cari;
     
    string a,b,pilihan;
    float x,y;
    cout<<"static int K[n+1]= {0,10,15,20,25,40,45};";
    cout<<"\nMasukkan nama kamu : ";
    cin>>a;
    cout<<"masukkan nama teman kamu : ";
    cin>>b;
    cout<<"nama saya adalah "<<a<<endl;
    cout<<"nama teman saya adalah "<<b<<endl;
    getch();
    cout<<"\n=====================================";
    cout<<"\nLayanan Sequential Search and Interpolation";
    cout<<"\n=====================================";
    cout<<"\nSelamat Menikmati";
    cout<<"\n=====================================";
    cout<<"\n1. Sequential Search",
    cout<<"\n2. Interpolation",
    cout<<"\n3. Exit",
    cout<<"\nMasukkan kode yang diinginkan [1..2] : ";cin>>kode;
    switch(kode)
 {
             
            case 1:
            cout<<"\n==================================";
            cout<<"\n1. Sequential Search";
            cout<<"\n==================================";
            {
                int nim;
                int I;
                int k;
                I=1;
                cout<<"\nMasukkan nilai yang ingin di cari : ";
                cin>>k;
                nim=k;
                while(K[I]!=nim)
                {
                  I=I+1;                          
                }
                if (I==(n+1))
                {
                  printf("search gagal");
                }
                else
                {
                  printf("\n  nim=%d ada di posisi=%d",nim,I=I+1);
                }
                getch();
             }

            case 2:
         
            cout << " \n2. Interpolasi Search ";
            cout << " \n==================================== ";

int A[10] = {20,15,5,18,10,35,40,25,4,19};
int i,j,k,tkr,low,high,pos,tm;

for(i=0;i<10;i++)
{
                 printf("data ke-%d:",i+1);
                 scanf("%d",&A[i]);
}
                 printf("Masukkan data yang akan anda cari:");
                 scanf("%d",&k);
               
                 for(i=0;i<10;i++)
                 {
                                  for(j=i+1;j<10;j++)
                 {
                                  if (A[i]>A[j])
                 {
                                  tkr=A[i];
                                  A[i]=A[j];
                                  A[j]=tkr;
                                  }
                                  }
                                  }
tm=0;
high=9;
low=0;
do
  {
      pos = ((k - A[low]) / (A[high] - A[low]))*(high-low)+low;
          if (A[pos] == k)
          {
                    tm++;
                    break;
          }
          if (A[pos] > k)
          high = pos-1;
               else
          if (A[pos] < k)
          low = pos + 1;
      }
  while (k >= A[low] && k<= A[high]);
  if (tm>0)
  {
           printf("Data %d yang dicari ada dalam array\n",k);
           }
  else
  {
      printf("data tidak di temukan dalam array\n");
}

}

getch();
}
   

Output :