Pencarian Biner

- Membandingkan kunci yang dicari dengan rekaman pada posisi tengah dari berkas.

- Bila sama (kasus 1) berarti rekaman yang diinginkan sudah ditemukan, atau kalau tidak sama (kasus2) berarti separuh dari rekaman-rekaman dalam berkas akan dieliminasi dari perbandingan yang selanjutnya. 

- Bila yang terjadi adalah kasus 2 maka proses pembandingan terhadap rekaman pada posisi tengah dilanjutkan menggunakan rekaman-rekaman yang tersisa.

Proc pencarian_biner
/* n buah rekaman diurutkan menaik menurut kunci rekaman */

AWAL :=1
Akhir := n
  While AWAL ≤ AKHIR do
  tengah := [ (awal+akhir)/2]
  if kunci (cari) = kunci (tengah)
  then pencarian berakhir.
  else if kunci(cari) > kunci (tengah)
  then AWAL := TENGAH + 1
  else AKHIR := TENGAH – 1
 end
rekaman tidak ditemukan
end pencarian_biner
 

Flowchart pencarian biner

Tengah = [ (awal + akhir)/2 ]

- Jika kunci cari < kunci tengah, maka bagian berkas mulai dari kunci tengah sampai akhir berkas dieliminasi. 

- Jika kunci cari > kunci tengah , maka bagian berkas mulai dari depan sampai dengan kunci tengah dieliminasi.
-  Jika Awal >Akhir maka rekaman tidak ditemukan.
- Pembulatan angka untuk hasil nilai tengah adalah pembulatan ke bawah.

 Contoh Soal :

1.Berikut akan dicari rekaman dengan kunci 49, berapa probe yang dilakukan untuk mendapatkannya?

Keterangan :
      Bilangan yang dicetak tebal menunjukkan rekaman yang sedang dibandingkan dan tanda kurung membatasi bagian berkas yang tersisa yang masih harus diperbandingkan. Tanda [ untuk AWAL dan tanda ] untuk AKHIR.
 
Perhitungan
   1     2    3    4    5     6     7    8    9

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

Perhitungan:
- TENGAH1 = [ (1 + 9)/2] = 5 → Kcari : Ktengah1 → 49 > 38
→ AWAL = TENGAH1 + 1 = 6 

- TENGAH2 = [ (6 + 9)/2 ] = 7 → Kcari : Ktengah2 → 49 > 48
→ AWAL = TENGAH2 + 1 = 8
 
- TENGAH3 = [ (8 + 9)/2] = 8 → Kcari : Ktengah 3 → 49 = 49
Ketemu, di Probe = 3

Perhitungan

   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]

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



2. Berikut akan dicari rekaman dengan kunci 27.

    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

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

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

Perhitungan :
 
- TENGAH1 = [ (1 + 9)/2] = 5 → Kcari : Ktengah1 → 27 < 38
→ AKHIR = TENGAH1 - 1 = 4
 
- TENGAH2 = [ (1 + 4)/2 ] = 2 → Kcari : Ktengah2 → 27 > 25
→ AWAL = TENGAH2 + 1 = 3
 
- TENGAH3 = [ (3 + 4)/2] = 3 → Kcari : Ktengah 3 → 27< 28
→ AKHIR = TENGAH3 – 1 = 2

AWAL > AKHIR → Rekaman tidak ditemukan.



Sumber : Kuliah Sistem Berkas - TI UNPAR - TAHUN 2012

Pencarian Secara Sekuensial

     Memproses rekaman-rekaman dalam berkas sesuai urutan keberadaan rekaman-rekaman tersebut sampai ditemukan rekaman yang diinginkan atau semua rekaman terbaca. 

Organisasi Berkas Sekuensial

     Dalam berkas sekuensial, rekaman yang ke i+1 akan diletakkan tepat sesudah rekaman ke i, contoh :

Akses
  Sesuai dengan namanya ,berkas sekuensial sangat cocok untuk akses yang sekuensial, misal dalam aplikasi dimana sebagian besar atau semua rekaman akan diproses.

Sebagai contoh adalah membuat daftar semua mahasiswa dalam sebuah Jurusan, seperti contoh berikut :



- Untuk membaca rekaman dengan nama mahasiswa “Dewi Sartika” diperlukan probe (akses terhadap lokasi yang berbeda) sejumlah 5 kali.
- Apa yang harus dilakukan agar kinerja pembacaan rekaman lebih baik?
-  Rekaman-rekaman berkas mahasiswa diurutkan berdasarkan nilai kunci “Nomor Mahasiswa”
-  Kolom “Nomor Mahasiswa” menunjukkan nilai yang urut dari kecil ke besar, atau

Kunci1
Hasil pengurutan berkas rekaman mahasiswa urut “Nomor Mahasiswa” adalah sebagai berikut :

 

(a). Berapa banyak Probe yang dibutuhkan untuk mendapatkan “Juli” pada urutan nyata bulan-bulan dalam system penanggalan?

(b). Berapa Probe yang dibutuhkan untuk mendapatkan ”Rabu” pada urutan nyata hari-hari dalam sistem waktu?

Jawaban :
(a). ”Juli” dalam kalender berada di urutan 7 jadi untuk mendapatkan ”Juli” dibutuhkan 7 probe.

(b). Bulan dalam kalender jika diurutkan secara alphabet menghasilkan Agustus, April, Desember, Februari, Januari, Juli, Juni, Maret, Mei, November, Oktober, September dibutuhkan 6 probe untuk mendapatkan ”Juli”.

Sumber : Kuliah Sistem Berkas - TI UNPAR - Tahun 2012