Algoritma Pencarian Data Dengan Metode Interpolasi

Interpolation search (Pencarian Interpolasi) adalah metode pencarian dengan cara mencari letak/posisi data yang akan dicari.  Data harus diurutkan secara ascending  lebih dahulu sebelum melakukan pencarian data.

 Rumus mencari posisi :

• Jika data[posisi] > data yg dicari, Akhir = posisi – 1
• Jika data[posisi] < data yg dicari, Awal = posisi + 1
• Jika Awal

Pencarian interpolasi tidak mencari posisi TENGAH seperti halnya algoritma pencarian biner, melainkan mencari posisi berikutnya dimana data yang dicari berada.

Contoh :

Diketahui data :
    1      2     3    4     5     6     7     8      9  (Posisi)
[ 21, 25, 28, 33, 38, 39, 48, 49, 69]
  
Carilah data 27 dan 49?

Cari Data 27
Awal = 1, Akhir =9
Cari data selama awal < Akhir

Data[2]=27?  Tidak
Data[2]<27 3="" akhir="9<br" awal="Posisi" ya=""> 

Data[3]=27? Tidak
Data[3]<27 -1="2," akhir="posisi" awal="3<br" tidak.="">Hasil : Data  tidak ditemukan karena awal>akhir
 
Cari data 49
Awal =1, Akhir =9
Cari data selama awal < Akhir    

Data[6]=49? Tidak
Data[6]<49 akhir="9<br" awal="posisi" ya.=""> 

Data[8]=49? Ya. Data ditemukan.

Berdasarkan algoritma interpolasi di atas, maka kita dapat membuat program pascal pencarian data sebagai berikut :

Program pencarian data dengan algoritma Interpolasi pada pembahasan ini merupakan pengembangan dari Contoh program algoritma interpolasi tanpa fungsi dan prosedur. Jadi program berikut adalah pencarian data dengan algoritma interpolasi menggunakan fungsi dan prosedur.

Program lengkap dengan source code sebagai berikut :

Program Interpolasi;
uses crt;

Type matrix =  array[1..50] of integer;

Procedure input(var n: integer; var data:matrix);
var i:integer;
Begin
   randomize;
   Write ('Masukkan banyak data : '); Readln (n);
   write('Data input = ');
    For i:= 1 to n do
    BEGIN
      data[i]:=random(50);
      write(' ',data[i],' ');
    End;writeln;
End;

Function Urutkan(n: integer; data :matrix; var urut:matrix):integer;
var i,j,y: integer;
Begin
    For i:= 1 to n do
    Begin
        For j:= 1 to n do
        If Data[i]        Begin
            y:=Data[i];
            Data[i]:=Data[j];
            Data[j]:=y;
        End;
    End;
    urut:=data;
End;

Procedure Cetak(n : integer; data : matrix);
var i: integer;
Begin
   write('Data Ascending = ');
   for i:=1 to n do
   write(' ',data[i], ' ');
   writeln;
End;

Function Cari(var cari:integer):integer;
Begin
   write('Tentukan Data yang dicari = ');readln(cari);
   writeln;
End;

Procedure Caridata(n,cari: integer; data:matrix);
var l,h,t,pos : integer; p:real;
label Selesai;
Begin
   l:=1; h:=n; t:=0;
   while (data[l]<=cari) and (data[h]>=cari) do
   Begin
      p:=l+((cari-data[l])/(data[h]-data[l]))*(h-l);
      pos:= round(p);
      if data[pos]=cari then
        Begin
           t:=1;
           goto selesai;
        End;
       Begin
       if data[pos]>cari then
          h:=pos-1
       else
          l:=pos+l;
       End;
       if l>h then goto selesai;
   End;
        Selesai:
            if t=1 then write('Data ditemukan')
              else write('Data tidak ditemukan');
   writeln;
  End;

{Program Utama}
var A,B : matrix;
    n,c: integer;
    ya : char;
Begin
  clrscr;
  ya:='y';
  input(n,A);
  while ya='y' do
  Begin
    Urutkan(n,A,B);
    Cetak(n,B);
    cari(c);
    Caridata(n,c,B);
    write('Ulangi?? (y/t) : ');readln(ya);
  End;
End.

Output program :

Demikian program pencarian data dengan algoritma interpolasi. Semoga bermanfaat.

God bless you all