Kasus 8.2 : Pencarian Biner (Binary Search).

Pada kesempatan ini saya akan memposting Program dari materi SEARCHING AND SORTING , program ini akan dibuat dalam Dev C++ .

Algoritma :



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


Dan ini kodingan Program C++ yang Menggunakan Aplikasi Dev C++ :

#include <iostream>
#define UKURAN 15

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

using namespace std;

void cetakHeader(void){
int i;
cout<<"\nSubscript : \n";
for (i=0;i<=UKURAN-1;i++) cout<<i<<" ";
cout<<"\n";
for (i=1; i <= 4*UKURAN; i++) cout<<"-";
cout<<"\n";
}
void cetakBaris(int b[], int low, int mid, int high){
int i;
for (i=0; i<=UKURAN-1; i++)
if (i<low || i>high) cout<< " ";
else if (i==mid) cout<< "*" <<b[i];
else cout<<b[i] << " ";
cout<<"\n";
}
int pencarianBiner(int b[], int kunciPencarian, int low, int high){
int i, middle;
while (low <= high) {
middle = (low+high) / 2;
cetakBaris(b, low, middle, high);
if (kunciPencarian == b[middle])
return middle;
else if (kunciPencarian < b[middle])
high = middle - 1;
else low = middle + 1;
}
return -1;
}

int main(int argc, char** argv) {
int a[UKURAN], i, kunci, hasil;
for (i=0; i<=UKURAN-1; i++) a[i] = 2*i;
cout<<"Masukkan bilangan antara 0-28 : ";
cin>>kunci;
cetakHeader();
hasil=pencarianBiner(a,kunci,0,UKURAN-1);
if (hasil != -1) cout<<kunci<<" ditemukan pada posisi : "<< hasil;
else
cout<<kunci<<" tidak ditemukan";

return 0;
}