Senin, 26 Desember 2011

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