Rabu, 20 April 2011

Membuat Program Pascal/Algoritma Pencarian "2"

  Agus Nur Ikhsan       Rabu, 20 April 2011

Pencarian Biner


Pencarian Biner (Bah.Ingg: Binary Search) adalah pencarian data secara eliminasi biner berulang/terus-menerus. Maksudnya adalah pada saat pencarian data, 1 kelompok data yang sudah urut dibagi menjadi 2 subkelompok. Lalu salah satu subkelompok dieliminasi, sehingga ruang lingkup pencarian data menjadi lebih sedikit. Kemudian subkelompok yang tersisa dibagi lagi menjadi 2 subkelompok lagi, demikian dilakukan secara berulang-ulang.



Apabila kelompok data ini dibagi 2, ternyata di bagian tengah terdapat nama Leny. Maka subkelompok data sesudah Leny akan dieliminasi, karena tidak mungkin nama Irawan akan terdapat pada data huruf L s/d Z. Sedangkan, subkelompok sebelum Leny, kemudian akan dibagi 2 lagi, dan diperiksa ulang. Ternyata kali ini di bagian tengah terdapat nama Gery. Maka kelompok data sebelum Gery akan dieliminasi, karena tidak mungkin terdapat data Irawan pada huruf A s/d G. Demikian seterusnya terjadi, proses eliminasi ruang lingkup pencarian data menjadi semakin sedikit secara berulang.
Berikut adalah 3 fakta penting mengenai pencarian biner:
  • Hanya bisa berfungsi pada data yang sudah terurut (sorted), ini adalah syarat mutlak dari pencarian biner
  • Merupakan salah satu contoh penerapan cara kerja dari konsep Divide and Conquer
  • Kompleksitasnya adalah O(lg n)
Ini adalah implementasi dari pencarian biner memakai function untuk pencarian data bertipe string:
type
TArrString = array of string;

function CariBiner(var Arr: TArrString; Cari: string): LongInt;
var
Awal, Akhir, Tengah, Ketemu: LongInt;

begin
Awal:= Low(Arr);
Akhir:= High(Arr);
Ketemu:= -1;
while (Awal <= Akhir) and (Ketemu = -1) do begin
Tengah:= (Awal + Akhir) shr 1;
if Arr[Tengah] = Cari then Ketemu:= Tengah else begin
if Cari < Arr[Tengah] then Akhir:= Tengah-1 else Awal:= Tengah+1;
end;
end;
CariBiner:= Ketemu;
end;

Penjelasannya Sebagai Berikut:
type
TArrString = array of string;

function CariBiner(var Arr: TArrString; Cari: string): LongInt;
var
Awal, Akhir, Tengah, Ketemu: LongInt;

begin
Awal:= Low(Arr);
Akhir:= High(Arr);
Ketemu:= -1;
while (Awal <= Akhir) and (Ketemu = -1) do begin
Tengah:= (Awal + Akhir) shr 1;
if Arr[Tengah] = Cari then Ketemu:= Tengah else begin
if Cari < Arr[Tengah] then Akhir:= Tengah-1 else Awal:= Tengah+1;
end;
end;
CariBiner:= Ketemu;
end;
logoblog

Thanks for reading Membuat Program Pascal/Algoritma Pencarian "2"

Previous
« Prev Post

Tidak ada komentar:

Posting Komentar