Berbeda dengan pencarian biner yang memilih posisi rekaman yang akan
diperbandingkan berikutnya sebagai tepat berada ditengah sisa berkas yang belum
diperiksa. Pencarian interpolasi tidak mencari posisi TENGAH seperti halnya algoritma
pencarian biner, melainkan menentukan posisi berikutnya, dengan menggunakan
algoritma sebagai berikut :
Proc
pencarian_interpolasi
/*
n buah rekaman dalam berkas diurutkan menaik menurut kunci rekaman */
AWAL := 1
Akhir := n
while AWAL ≤ AKHIR do
BERIKUT :=
if kunci (cari) = kunci (berikut)
then pencarian berakhir.
else if kunci (cari) > kunci (berikut)
then AWAL := berikut + 1
else AKHIR := berikut – 1
End
Rekaman
tidak ditemukan
End
pencarian_biner
Untuk
rekaman dengan susunan sebagai berikut, berapa probe untuk menemukan rekaman
dengan kunci 49 bila digunakan pencarian interpolasi.
1 2 3
4 5 6 7
8 9
[21 25 28 33
38 39 48 49 69]
21 25 28 33
38 39 [48 49 69]
Perhitungan
:
BERIKUT1
=
=
5,6666 , dibulatkan 6
Kcari
: Kberikut = 49 > 38 AWAL = BERIKUT1 + 1 = 6 +
1 = 7
BERIKUT2 =
|
Kcari : Kberikut2 = 49 = 49
ketemu, probe 2