Pages

▼

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

Tidak ada komentar:

Posting Komentar

Terima Kasih sudah berkunjung kawan.
Mohon Meninggalkan Jejak dengan Berkomentar.
Salam Blogger !!

TUHAN Memberkati Kita Semua...