Binary Search

Dalam Pencarian Binary Search, Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian. Adalah teknik pencarian data dalam dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian. Prinsip pencarian biner adalah:

Data diambil dari posisi 1 sampai posisi akhir N Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar? Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1 Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1 Jika data sama, berarti ketemu



contoh program binary search

//binary searching,
//program bisa jalan jika data sudah terurut
#include
#include

int data[10]={1,3,4,7,12,25,40,65,78,90};
int binary_search(int cari)


{
int l,r,m;
int n=10;
l=0;
r=n-1;
int ketemu=0;
while (l<=r && ketemu==0)
{
m=(l+r)/2;
if (data[m]==cari)
ketemu=1;
else
if(carir=m-1;
else l=m+1;
}
if(ketemu==1) return 1; else return 0;
}

void main()
{
clrscr();
int cari, hasil;
cout<<"masukan data yang ingin di cari= ";
cin>>cari;
hasil = binary_search(cari);
if(hasil==1)
{
cout<<"data ada!"<}
else
if(hasil==0)
cout<<"data tidak ada!"<getch();
}

contoh ke dua

#include
#include

int cari_biner(int array[],int ukuran, int elemen);

void main()
{
const int ukuran=10;
int array[ukuran]={0,6,9,12,20,23,29,32,47,79};
cout<<"isi dari array : "<for(int i=0;icout<<" "<
int elemen;
int tanda;
cout<<"\n masukkan data yang dicari : ";
cin>>elemen;

tanda= cari_biner(array,ukuran,elemen);
if (tanda!=-1)
cout<<"\n data tersebut ditemukan pada posisi : array["<<
tanda<<"],"<<" atau deret ke-"<<(tanda+1);

else
cout<<"\n data tersebut tidak ditemukan ";
getch();

}

int cari_biner(int array[],int ukuran,int elemen)
{
int start=0;
int end=ukuran - 1;
int middle;
int posisi=-1;
middle=(start + end ) / 2;
do
{
if(elemenend=middle-1;
else if (elemen>array[middle])
start=middle+1;
middle=(start+end)/2;

}
while(start<=end && array[middle]!=elemen);

if(array[middle]==elemen)
posisi=middle;
return posisi;

}

Sumber: http://allaboutalgoritma.blogspot.com/2009/06/binary-search.html