Tugas Struktur Data

1.Pengertian  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 :

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

 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.   
2. contoh algoritma dalam 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  

3. contoh flowchart  Interpolation Search

 

untuk contoh program bisa di lihat di :

contoh program iterpolation search