ALGORITMA PENCARIAN BINER (BINARY SEARCH)

Pencarian Biner (Binary Search) pada array yang sudah terurut

Pencarian Biner (Binary Search) dilakukan untuk :

♪   memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.

♪   Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

♪   Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

ALGORITMA  

Kamus

      Const N : integer = 8  { misalkan jumlah elemen array maksimum = 8 }

      Type A = array [ 1 ..... N ] of integer

      Cari, BatasAtas, BatasBawah, Tengah : Integer

      Ketemu : boolean

ALGORITMA

         Input (cari) { meminta nilai data yang akan dicari}

         BatasAtas     ¬  1 { indeks array dimulai dari 1 }

         BatasBawah     ¬   N    

         Ketemu   ¬  False

         While (BatasAtas < BatasBawah) and (not ketemu) do

               Tengah ¬   (BatasAtas  + BatasBawah) div 2

               If A [Tengah] = cari then

                  Ketemu ¬ true

                           Else

                                 If ( A [Tengah]  < cari ) then { cari di bagian kanan }

                                       BatasAtas ¬ Tengah + 1

                                 Else

                                       BatasBawah ¬ Tengah – 1 { cari di bagian kiri }

                                 Endif

                           Endif

         EndWhile

         If (ketemu) then

                     Output ( ‘Data berada di index nomor’, Tengah )

         Else     Output ( ‘Data tidak ditemukan’ )

         Endif

Contoh Nilai-Nilai data yang sudah terurut :

A	2	5	8	12	15	25	37	57
	1	2	3	3	5	6	7	8

Kasus 1  : cari = 12

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 + 8) div 2 = 4

                           A [Tengah] = A [4] = 12, berarti loop pertama data langsung ditemukan

Kasus 2  : cari = 15

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 +  8) div 2 = 4

                           A [Tengah] = A [4] = 12 < cari = 15, berarti BatasAtas = Tengah + 1 = 4 + 1 = 5

Loop kedua :     Tengah = (BatasAtas + BatasBawah) div 2 = (5 +  8) div 2 = 6

                           A [Tengah] = A [6] = 25 > cari = 15, berarti BatasBawah = Tengah - 1 = 6 - 1 = 5

Loop ketiga :     Tengah = (BatasAtas + BatasBawah) div 2 = (5 +  5) div 2 = 5

                           A [Tengah] = A [5] = 15, berarti  setelah loop ketiga, data ditemukan

Kasus 3  : cari = 10

Loop pertama : Tengah = (BatasAtas + BatasBawah) div 2 = (1 +  8) div 2 = 4

                           A [Tengah] = A [4] = 12 > cari = 10, berarti BatasBawah = Tengah - 1 = 4 - 1 = 3

Loop kedua :     Tengah = (BatasAtas + BatasBawah) div 2 = (1 +  3) div 2 = 2

                           A [Tengah] = A [2] = 5 < cari = 10, berarti BatasAtas = Tengah + 1 = 2 + 1 = 3

Loop ketiga :     Tengah = (BatasAtas + BatasBawah) div 2 = (3 +  3) div 2 = 3

                           A [Tengah] = A [3] = 8, berarti  setelah loop ketiga, data tidak ditemukan

Untuk jumlah data sebanyak n, maka proses pembandingan maksimal sebanyak ( log n ) kali. Untuk contoh di atas, jumlah data 8, maka proses pembandingan maksimal sebanyak 3 kali.

Posted in: Teori Pascal