Binary Search

 

Binary search adalah algoritma pencarian untuk data yang terurut. Pencarian dilakukan dengan cara menebak apakah data yang dicari berada ditengah-tengah data, kemudian membandingkan data yang dicari dengan data yang ada ditengah. Bila data yang ditengah sama dengan data yang dicari, berarti data ditemukan. Namun, bila data yang ditengah lebih besar dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan berada disebelah kiri dari data tengah dan data disebelah kanan data tengah dapat diabai. Upper bound dari bagian data kiri yang baru adalah indeks dari data tengah itu sendiri. Sebaliknya, bila data yang ditengah lebih kecil dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan besar berada disebelah kanan dari data tengah. Lower bound dari data disebelah kanan dari data tengah adalah indeks dari data tengah itu sendiri ditambah 1. Demikian seterusnya.

Ilustrasi

 

Perhatikan ilustrasi berikut ini:

Contoh binary search :

Rekursif

BinarySearch(A[0..N-1], value, low, high)

{

if (high < low)

return -1 // not found

mid = (low + high) / 2

if (A[mid] > value)

BinarySearch(A, value, low, mid-1)

else if (A[mid] < value)

BinarySearch(A, value, mid+1, high)

else

return mid // found

}

 

Interatif

BinarySearch(A[0..N-1], value)

{

low = 0

high = N – 1

while (low <= high)

{

mid = (low + high) / 2

if (A[mid] > value)

high = mid – 1

else if (A[mid] < value)

low = mid + 1

else

return mid // found

}

return -1 // not found

}

Keunggulan Binary Search

Keunggulan utama dari algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah tabel lebih kecil daripada waktu yang dibutuhkan algoritma sequential search.

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.


LISTING PROGRAM

program Binary_Search;

uses wincrt;

const

x = 10;

 

Var

arr : array [1..x] of integer;

i, kiri,tengah,kanan,cari :integer;

ketemu :boolean;

 

Begin

clrscr;

writeln(‘List Angka : ‘);

for i := 1 to x do

begin

arr[i] := i;

write(arr[i],’ ‘);

end;

writeln;

write(‘Masukan data yang dicari (dgn Binary Serach) : ‘);

readln(cari);

kiri:=x;

kanan:=1;

ketemu:=false;

while not(ketemu) do

begin

tengah:=(kiri + kanan) div 2;

If arr[tengah]=cari then

begin

ketemu:=true;

writeln(‘Kunci yang di cari berada pada index ke ‘,tengah);

end

else if (cari < arr[tengah]) then

kiri := tengah – 1

else

kanan:= tengah+1;

if (kanan > kiri) then

begin

ketemu:=true;

writeln(‘Data yang Anda cari tidak ada !’);

end;

end;

readln;

end.

PRINT OUT

Misalkan yang dicari adalah angka 4, maka hasilnya adalah :