Cara kerja Interpolation Search

Cara kerja metode pencarian interpolasi dapat
disimulasikan sebagai berikut, dimisalkan memiliki data
terurut seperti di bawah ini:
Contoh Data :

Indeks Konversi Kombinasi Gejala (+)
[0] 25 AJKMOPQRST
[1] 34 JMOPQRS
[2] 41 AJKMQRST
[3] 56 AJMOQS
[4] 63 AJKMOQS
[5] 72 JKMOPST
[6] 88 MOPQRST
[7] 96 KMPQRST

Penyelesaian 1:
Data yang dicari = 60
o Kunci Pencarian ? 60
o Min=0, Max=7
o Posisi = (60 - 25) / (96 - 25) * (7 - 0) + 0 = 3,45 = [3]
o Kunci[3] < data yang dicari (60),
o min=posisi+1 = 3 + 1 = [4],
Ulangi perhitungan
o Min=4, Max=7
o Posisi = (56 - 25) / (96 - 56) * (7 - 4) + 4 = 6,32 = [6]
o Kunci[6] adalah 88 yang lebih besar dari kunci yang
dicari dicari (56). Sehingga data tidak ditemukan.

Penyelesaian 2:
Data yang dicari = 41
o Kunci Pencarian ? 41
o Min=0, Max=7
o Posisi = (41 – 25) / (96 – 25) * (7 – 0) + 0 = 1,57 = [1]
o Kunci[3] < data yang dicari (41),
o min=posisi+1 = 1 + 1 = [2],
Ulangi perhitungan
o Min=2, Max=7
o Posisi = (41 – 41) / (96 – 41) * (7 – 2) + 2 = 2 = [2]
o Kunci[2] adalah 41 sedangkan data yang dicari adalah
41 sehingga data ditemukan.

• Algoritma Interpolation Search
1. Banyaknya record array (k)
2. Nilai awal min=0 ; max=k-1
3. Hitung mid= min + ((kunci - k[min]) * (max - min)) /
(k[max] – k[min])
4. Bandingkan data yang dicari(kunci) dengan data posisi
tengah(mid)
5. Jika lebih kecil, proses dilanjutkan dengan posisi max =
posisi tengah-1
6. Jika lebih besar, proses dilanjutkan dengan posisi
min=posisi tengah+1
7. Jika data posisi tengah(mid) = data yang dicari(kunci) ,
maka index=mid, selesai
8. Jika min<=max dan k[mid]=!kunci, maka ulangi
langkah 3
9. Jika k[mid]=!kunci, maka index=-1, selesai.

Flowchart :