Pencarian Interpolasi pada Sistem Berkas

Berbeda dengan pencarian biner yang memilih posisi rekaman yang akan dibandingkan berikutnya tepat ditengah berkas yang belum diperikasa, pencarian interpolasi adalah menentukan posisi yang diestimasi dari sisa rekaman yang belum diperiksa.(Asumsinya Numeris). Algoritma pencarian interpolasi memiliki kerumitan dalam hal perhitungan untuk menentukan posisi rekaman yang akan diperiksa berikutnya dibandingkan dengan pencarian biner tetapi algoritma pencarian interpolasi memiliki kinerja yang baik untuk rekaman-rekaman yang memiliki kunci yang mendekati seragam.

Rumus :
awal = 1
akhir = n
Berikut = awal + (Nilai cari – Nilai awal)/(Nilai Akhir – Nilai Awal) x (Akhir – Awal)
Jika Kunci Cari > Kunci Berikut maka Kunci berikut + 1
Jika Kunci Cari < Kunci Berikut Maka Kunci Berikut – 1
Contoh :
anda memiliki rekaman 10,20,30,40,50,60,70,80,90.kita mau mencari nilai 80
Langkah-langkah :
Iterasi I
awal = 1 => merupakan kunci awal
akhir = 9 => merupakan kunci akhir

berikut = 1 + (80 – 10)/(90 – 10) x (9 -1) =(1 merupakan kunci awal, 80 merupakan nilai cari, 10 merupakan nilai awal,90 adalah nilai akhir)

= 1 + (70)/(80) x (8)
= 1 + (0,875) x (8)
= 1 + (7)
= 8
Kc : Kb => 80 = 80
Ketemu pada iterasi pertama