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