Algoritma Binary Search

Binary Search adalah salah satu algoritma pencarian yang tercepat. Kecepatan algoritma ini hanya bisa dikalahkan oleh teknik hashing, yang tidak akan dibahas di sini. Untuk mencari jutaan data, Binary Search hanya butuh O(log N) kali pembandingan (sekitar 20 kali), sedangkan Linier Search butuh O(N) pembandingan (sekitar 500.000 kali). Tapi yang harus dicatat di sini, data yang dicari harus sudah terurut!
Algoritma iteratif (contohnya yang menggunakan perputaran FOR, WHILE, dsb) pada umumnya dapat dengan mudah diubah ke dalam algoritma rekursif (memanggil dirinya sendiri). Keistimewaan algoritma iteratif adalah sederhana, cepat, dan menggunakan sedikit memori. Sedangkan pada kasus seperti menelusuri pohon, algoritma rekursif jelas lebih baik karena lebih mudah difahami.
Pada prinsipnya, Binary Search adalah membandingkan Key (angka yang dicari) dengan angka yang berada tepat di tengah-tengah deretan angka yang sudah terurut. Jika sama, maka itulah yang dicari. Tapi jika tidak sama, maka deretan data dipecah menjadi dua blok: Blok bawah (kecil) dan blok atas (kecil). Lalu proses diulangi terhadap blok bawah atau blok atas, tergantung besarnya Key apakah lebih kecil ataukah lebih besar daripada data yang berada di tengah-tengah tadi.berikut contoh algoritmanya :

#include
#include

int binarySearch(int sortedArray[], int awal, int akhir, int key) {
if (awal <= akhir) {
int tengah = (awal + akhir) / 2; // Hitung titik tengah.
if (key == sortedArray[tengah])
return tengah; // Ketemu.
else if (key < sortedArray[tengah])
// Panggil prosedur binarySearch untuk setengah bagian bawah.
return binarySearch(sortedArray, awal, tengah-1, key);
else
// Panggil prosedur binarySearch untuk setengah bagian atas.
return binarySearch(sortedArray, tengah+1, akhir, key);
}
return -(awal + 1); // Gagal menemukan Key yang dicari.
}

void main(void) {
int sortedArray[100];
int jumlahData, i, key;
int letak;

cout << "Demo Binary Search menggunakan teknik rekursi" << endl;
cout << "Oleh: (Ketik nama anda di sini)." << endl;
cout << endl;
cout << "Ada berapa banyak data? (max 100) "; cin >> jumlahData;
cout << endl;
cout << "Silakan Ketik " << jumlahData << " angka yg sudah terurut!" << endl;
cout << "Tiap angka dipisahkan oleh spasi." << endl;

for (i = 0; i < jumlahData; i++) {
cin >> sortedArray[i];
};

cout << endl;
cout << "Angka berapa yang dicari? "; cin >> key;
cout << endl;
cout << "Mulai mencari..." << endl;
letak = binarySearch(sortedArray, 0, (jumlahData - 1), key);
if (letak < 0) {
cout << "Maaf, data tidak ketemu." << endl;
}
else {
cout << "Data ditemukan pada posisi ke " << (letak + 1) << endl;
cout << "Pada posisi tsb terdapat angka " << sortedArray[letak] << endl;
};
cout << endl;
cout << "Tekan sembarang tombol.";
getch();
}