Pencarian Biner (Binary Search)

Pada algoritma pencarian biner, data sudah dalam keadaan terurut (untuk mudahnya diasumsikan urut naik). Contoh dalam kehidupan sehari-hari, seperti orang mencari nomor telepon pada buku telepon. Setiap kali pencarian, kunci akan selalu dibandingkan dengan data yang berada di tengah (middle), bila sama berarti data ketemu, bila tidak, akan “dilihat” apakah data ada di sebelah “kiri” (artinya data lebih kecil dari data di tengah) atau di sebelah “kanan” (artinya data lebih besar dari data di tengah). Bila data ada di sebelah kiri, dilakukan pencarian dengan cara yang sama (sementara data yang berada di sebelah kanan akan diabaikan). Jadi, setiap kali pencarian, data selalu “dibelah” menjadi dua bagian (biner), sampai pada “titik tertentu” (bila sama dengan titik tengah, pencarian tidak dilakukan lagi, bila tidak, sampai pada perbandingan terakhir data juga tidak sama, berarti data tidak ditemukan pada array aray).

Berikut adalah algoritmanya:

function pencarianBiner(input aray : larik; kunci, low, high : integer) : integer

Deklarasi ketemu : boolean i, middle : integer

Deskripsi ketemu € false while (low <= high) and (not ketemu) do middle € (low+high) div 2 if (kunci = aray[middle]) then ketemu € true { data pencarian = data di tengah } else if (kunci < aray[middle]) then high € middle – 1 {data akan dicari lagi di sebelah kiri} else low € middle + 1 {data akan dicari lagi di sebelah kanan} endif endwhile if ketemu then pencarianBiner := middle else pencarianBiner := -1; endif berikut adalah pemrogramannya #include <iostream> using namespace std; int funcbinary (int data[], int n, int k) {  int atas,bawah,tengah,posisi;  bool ada;  ada    = false;  bawah  = 0;  atas   = n - 1;  posisi = -1;  while (bawah <= atas)  {   tengah = (atas + bawah) / 2;   if (k == data[tengah])   {    posisi = tengah;    break;   }  else if (k < data[tengah]) atas = tengah - 1;  else if (k > data[tengah]) bawah= tengah + 1;  }  return posisi; } int main () {  int kk;  cout << "INPUT ANGKA : "; cin >> kk;  int n         = 10;  int data[] = {21,31,48,52,64,78,87,92,105,170};  int k      = kk;  int posisi = funcbinary (data,n,k);  if (posisi != -1)  {   cout << "ANGKA " << k << " ditemukan pada indeks ke-" << posisi << endl;  }  else  {   cout << "ANGKA " << k << " tidak ditemukan" << endl;  }  return 0; }