Pencarian Interpolasi

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