Pencarian Interpolasi

Pencarian Interpolasi (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 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 :

Terima kasih telah mengunjungi blog saya semoga sedikit ilmu ini dapat bermanfaat bagi anda.

SHARE

Milan Tomic

Hi. I’m Designer of Blog Magic. I’m CEO/Founder of ThemeXpose. I’m Creative Art Director, Web Designer, UI/UX Designer, Interaction Designer, Industrial Designer, Web Developer, Business Enthusiast, StartUp Enthusiast, Speaker, Writer and Photographer. Inspired to make things looks better.

• 
• 
• 
• 
•