Binary Search dengan C++

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 <iostream.h>

#include <conio.h>

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(cari<data[m])

r=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!"<<endl;

}

else

if(hasil==0)

cout<<"data tidak ada!"<<endl;

getch();

}

contoh ke dua

#include <iostream.h>

#include <conio.h>

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 : "<<endl;

for(int i=0;i<ukuran;i++)

cout<<" "<<array[i];

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(elemen<array[middle])

end=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.co.id/2009/06/binary-search.html