Binary Searching

Binary adalah sebuah metode yang diterapkan pada sekumpulan data yang sudah terurut menaik atau menurun). Metode ini lebih cepa di banding pencarian beruntun dan data yang sudah terurut menjadi syarat mutlak untuk menggunakan metode ini.

Konsep Binary Search :
# Konsep dasar metode ini adalah membagi 2 jumlah elemen, yang menentukan apakah data yang berada pada elemen paling tengah bernilai sama, lebih dari atau kurang dari nilai data yang akan dicari.
# Jika bernilai sama, maka langsung data yang dicari ditemukan.dan jika data di elemen terurut naik, maka data yang berada di tengah kurang dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kanan, dan begitu seterusnya sampai ketemu atau tidak sama sekali.
# Sebaliknya untuk nilai data yang berada di tengah lebih dari data yang dicari, maka pencarian selanjutnya berkisar di elemen tengah ke kiri, dan begitu seterusnya sampai ketemu atau tidak sama sekali.
# Dan untuk data yang terurut menurun. Dalam hal ini menentukan indeks paling awal dan indeks paling akhir, untuk membagi 2 elemen yang ada.

Langkah - Langkah Binary Search :

1. Asumsikan data terurut secara horizontal dari indeks 0 sampai n-1, untuk menggunakan istilah kanan dan kiri.
2. Misalkan kumpulan data yang berjumlah n adalah larik L, dan data yang akan dicari adalah X.
3. Tentukan nilai indeks awal i = 0 dan indeks akhir j = n-1.
4. Tentukan apakah data terurut menurun atau menaik dengan menggunakan membandingkan apakah elemen paling kiri L[0] lebih dari atau kurang dari elemen paling kanan L[n-1].
Jika data di elemen paling kiri L[0] > data di elemen paling kanan L[n-1], maka data terurut menurun.
Jika data di elemen paling kiri L[0] < k =" (i" i =" k." k =" (i"> X, maka pencarian berikutnya dilakukan di sisi kiri indeks k, lakukan proses seperti pada nomor 6, dimana nilai indeks j sekarang sama dengan nilai indeks k sebelumnya.
j = k.
k = (i + j) div 2.
Dan seterusnya sampai nilai X dicari ketemu atau tidak sama sekali.
10. Jika data terurut menurun, maka tukar kondisi yang ada di nomor 8 dan 9.

Contoh program binary Search:
#include <iostream.h>
#include <conio.h>
int main(int argc, char* argv[])
{
int X,i,j,k,p;
int L[10] = {12,14,15,17,23,25,45,67,68,70};
/* Menentukan apakah terurutmenaik atau menurun */
/* variabel p digunakan untuk kode, apakah menaik atau menurun */
/* jika p = 0,maka data terurut menaik */
/* jika p = 1,maka data terurut menurun */
if (L[0]
{
printf("Data terurut menaik \n");
p = 0;
}
else
{
printf("Data terurut menurun \n");
p = 1;
}
/* input data X yang akan dicari */
printf("Data yang akan dicari = ");scanf("%d",&X);
/* penentuan indeks awal dan akhir semula */
i = 0;
j = 9;
/* proses perulangan untuk menentukan nilai tengah k */
do
{
k = (i + j) / 2;
if (p==0) // jika data terurut menaik
{
if (L[k]==X)
{
printf("Data ditemukan di elemen %d",k);
getch();
return 0; // langsung keluar program
}
else if (L[k]< X)
{
i = k;
}
else
{
j = k;
}
}
else // jika data terurut menurun
{
if (L[k]==X)
{
printf("Data ditemukan di elemen %d",k);
getch();
return 0; // langsung keluar program
}
else if (L[k]> X)
{
i = k;
}
else
{
j = k;
}
}
}
while(k!=0); // sampai nilai k = 0, iterasi berakhir
printf("Data tidak ditemukan!");
getch();
return 0;
}