Linear and Binary Search

Dalam algoritma pemrograman, ada banyak kasus di mana kita diharuskan mencari suatu value dalam kumpulan data. Misal dalam dunia nyata, kita memiliki 20 buah kardus, cari kardus mana yang memiliki tepat n buah buku di dalamnya.

Sebuah pencarian, atau search, setidaknya harus memiliki ketiga kriteria ini:

1. Teknik/algoritma search
2. Value/nilai yang dicari
3. Search space (ruang batas pencarian)

Dalam contoh di atas, teknik pencarian bisa menggunakan linear search atau teknik lainnya. Value yang dicari adalah kardus dengan n buah buku. Dan search space-nya adalah 20 buah kardus yang kita miliki.

Dalam post ini hanya akan dibahas mengenai Linear Search dan Binary Search.


Linear Search

Linear search atau metode pencarian linear adalah teknik pencarian di mana program akan mencari anggota dari suatu search space satu per satu sampai value yang dicari ditemukan. Kompleksitas pencarian adalah O(n).

Contoh kode dalam pascal:

//search technique : Linear Search
//search value     : x
//search space     : array of 20 integers

var
  arr : array [1..20] of integer = (1,6,2,8,30,3,7,3,4,8,12,19,53,63,85,13,63,85,3,100); //early initialization
  x,i : integer;
  ada : boolean;         //penanda, ada atau tidak
begin
  write('Angka yang ingin dicari: ');
  read(x);
  for i:=1 to 20 do
    if (arr[i]=x) then
    begin
      writeln('Angka ',x,' ditemukan di indeks ',i);
      ada := true;       // angka ditemukan
      break;
    end;
  if (not ada) then writeln('Angka ',x,' tidak ditemukan'); // angka tidak ditemukan
end.

Cobalah untuk input yang berbeda-beda.
Linear search untuk mencari suatu value dalam array dengan anggota 10000000 (sepuluh juta) elemen, memakan waktu sekitar ~1 detik (komputer pentium).

Binary Search

Binary search adalah metode pencarian dalam suatu search space (atau lebih sering arrays) yang telah terurut isinya, baik terurut menaik maupun menurun. Metode ini berjalan dengan kurang-lebih seperti ini:

1. Baca nilai yang ingin dicari (x)
2. Bila nilai yang terdapat di bagian tengah array = x, outputkan 'ADA', bila tidak, kalau mid > x, potong search space menjadi setengah (dari titik awal sampai tengah-1) bila mid < x, potong search space menjadi setengah (dari tengah+1 sampai titik akhir), ulangi sampai titik akhir-titik awal = 1.

 Binary search memiliki kompleksitas O(log n) dengan log basis 2.
Untuk lebih jelasnya, kode dalam pascal:

//search technique : Linear Search
//search value     : x
//search space     : array of 20 integers

var
  arr : array [1..20] of integer = (1,6,2,8,30,3,7,3,4,8,12,19,53,63,85,13,63,85,3,100); //early initialization
  x,i : integer;
  mid : integer;
  lef : integer;
  rit : integer;

procedure swap(var a,b:integer);   // procedure (dan fungsi), akan dibahas selanjutnya
var
  tmp : integer;
begin
  tmp := a;
  a   := b;
  b   := tmp;
end;

procedure sort();                  // sorting, akan dibahas di post-post berikutnya
var
  i,j : integer;
begin
  for i:=1 to 20 do
  begin
    for j:=2 to 20 do
      if (arr[j]>arr[j-1]) then
        swap(arr[j],arr[j-1]);
  end;
end;

begin
  sort();    //pertama-tama, sort dulu search space (array dalam kasus ini)
  write('Angka yang ingin dicari: ');
  read(x);

  lef:=1; rit:=20; //batas awal dan akhir search space (1..20)
  repeat
    mid := (lef+rit) div 2;
    if (arr[mid] > x) then
      rit:=mid-1
    else
      lef:=mid+1;
  until (arr[mid]=x) or (lef>rit);
  if (arr[mid] = x) then writeln('Angka ',x,' ditemukan di indeks ',mid)
  else writeln('Angka ',x,' tidak ditemukan'); // angka tidak ditemukan
end.

Cobalah untuk input yang berbeda-beda.
Algoritma binary search untuk mencari suatu value dalam array yang memiliki 10000000 (sepuluh juta) elemen hanya memakan waktu kurang lebih (log 10000000) = ~0.000023 detik.

Video tutorial Linear dan Binary Search (from YouTube):