Pencarian Interpolasi

- Pencarian merupakan proses yang fundamental dalam pengolahan data

-  Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu.

-  Teknik searching ini dilakukan dengan perkiraan letak data

Contoh ilustrasi:

Jika kita hendak mencari suatu kata di dalam kamus Komputer, misal yang berawalan dengan huruf M, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada 1/3 atau 1/4 dari tebal kamus.  

 -Pencarian interpolasi (asumsinya kunci rekaman numeris) menentukan posisi yg akan dibandingkan berikutnya berdasar posisi yang diestimasi dari sisa rekaman yg belum diperiksa.

-  Pencarian ini tidak mencari posisi TENGAH seperti halnya algoritma pencarian biner, melainkan menentukan posisi berikutnya.

- Algoritma pencarian interpolasi memiliki kerumitan dalam hal perhitungan untuk menentukan posisi rekaman yang akan diperiksa berikutnya dibandingkan dengan pencarian biner 

-  Algoritma pencarian interpolasi memiliki kinerja yang baik untuk rekaman-rekaman yang memiliki kunci yang mendekati seragam.

ALGORITMA PENCARIAN INTERPOLASI

AWAL := 1

Akhir := n

while AWAL  AKHIR do

                                 kunci (dicari) – kunci (AWAL) 

Berikut := [AWAL+ -----------------------------------------    (AKHIR-AWAL) ]

                                 Kunci (AKHIR) – kunci (AWAL) 

      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.

Contoh Implementasi 

                                            kunci (dicari) – kunci (AWAL)
Berikut := [AWAL + ---------------------------------------- x (AKHIR-AWAL) ]
                                             Kunci (AKHIR) – kunci (AWAL)

- Berapa probe untuk menemukan rekaman dengan kunci 49 bila digunakan pencarian interpolasi untuk rekaman dengan susunan sebagai berikut :
-  1      2     3    4     5     6     7     8      9
[ 21, 25, 28, 33, 38, 39, 48, 49, 69]

Hasil :



-  Berapa probe untuk menemukan rekaman dengan kunci 27 bila digunakan pencarian interpolasi untuk rekaman dengan susunan sebagai berikut :

[21, 25, 28, 33, 38, 39, 48, 49, 69]

Perhitungan : 

Sumber : Kuliah Sistem Berkas - TI UNPAR - Tahun 2012