Materi Kuliah

Bagi Mahasiswa AMIKOM yang mengambil mata kuliah sistem berkas untuk bahan UAS silahkan didownload

Pencarian Interpolasi Pada Sistem Berkas

Berbeda dengan pencarian biner yang memilih posisi rekaman yang akan dibandingkan berikutnya tepat ditengah berkas yang belum diperikasa, pencarian interpolasi adalah menentukan posisi yang diestimasi dari sisa rekaman yang belum diperiksa.(Asumsinya Numeris).

Algoritma pencarian interpolasi memiliki kerumitan dalam hal perhitungan untuk menentukan posisi rekaman yang akan diperiksa berikutnya dibandingkan dengan pencarian biner tetapi algoritma pencarian interpolasi memiliki kinerja yang baik untuk rekaman-rekaman yang memiliki kunci yang mendekati seragam.

Rumus :

awal = 1
akhir = n
Berikut = awal + (Nilai cari - Nilai awal)/(Nilai Akhir - Nilai Awal) x (Akhir - Awal)

Jika Kunci Cari lebih besar dari pada Kunci Berikut maka Awal sama dengan Kunci berikut ditambah satu
Jika Kunci Cari lebih kecil dari pada Kunci Berikut maka Akhir sama dengan Kunci berikut dikurangi satu

Contoh : anda memiliki rekaman 10,20,30,40,50,60,70,80,90.kita mau mencari nilai 80

Langkah-langkah:

Iterasi I

awal = 1 => merupakan kunci awal
akhir = 9 => merupakan kunci akhir
berikut = 1 + (80 - 10)/(90 - 10) x (9 -1) =>(1 merupakan kunci awal, 80 merupakan nilai cari, 10 merupakan nilai awal,90 adalah nilai akhir)

= 1 + (70)/(80) x (8)
= 1 + (0,875) x (8)
= 1 + (7)
= 8

Kc : Kb => 80 = 80Ketemu pada iterasi pertama

Pencarian Biner Pada Sistem Berkas

Pada rekaman yang sudah diurutkan dapat diperkecil dengan menggunakan pencarian biner. Jika kunci cari lebih kecil dari pada kunci tengah maka bagian berkas dimulai dari kunci tengah sampai akhir berkas dieliminasi. Sebaliknya jika kunci cari lebih besar dari pada kunci tengah maka bagian berkas dimulai dari awal berkas sampai kunci tengah

Rumus :

awal=1
akhir=n
tengah= 1+n/2

Jika Kc > Kt maka tengah +1
Jika Kc< Kt maka tengah - 1

contoh :

anda memiliki rekaman 10,20,30,40,50,60,70,80,90.kita mau mencari nilai 70

langkah-langkah :

iterasi I

awal = 1
akhir = 9 =>(didapat karena jumlah berkas 9)tengah = 1+9/2 = 5 =>5 merupakan nilai tengah

Kc : Kt = 70 > 50 =>(70 adalah nilai yang dicari & 50 adalah nilai yang didapat dari kunci tengah)

Awal = tengah + 1= 5+1=6 =>(5 merupakan kunci tengah)

Iterasi II

awal = 6
akhir = 9
tengah = 6+9/2 = 7.5 = 7 =>(nilai sisa dibuang sehingga menjadi 7)

Kc : Kt = 70= 70

Ketemu pada itersi II