A. Pengertian Searching
Searching adalah mencari data yang dibutuhkan. Searching dalam pemrograman bisa dilakukan untuk mencari data yang ada di dalam memory komputer.Dalam kehidupan sehari-hari kita juga sering melakukan kegiatan searching seperti mencari data/informasi yang ada dalam internet. Ada beberapa metode yang dapat digunakan untuk searching, ada yang dinamakan:
·
Sequential
Search
·
Binary
Search
B. Pengertian Binery Search
Salah satu syarat pencarian biner (Binary Search) yang dapat dilakukan adalah data sudah dalam keadaan terurut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita sering menggunakan pencarian biner, misalnya pada saat ingin mencari suatu kata dalam kamus.
Langkah dari pencarian
biner adalah sebagai berikut:
1. mula-mula diambil posisi awal=1 dan posisi akhir=n
2. kemudian kita cari posisi data tengah dengan rumus posisi tengah = (posisi awal
+ posisi akhir)
3. kemudian data yang dicari dibandingkan dengan data tengah
a. jika sama, data ditemukan, proses selesai.
b.
jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama
dengan posisi
tengah - 1.
tengah - 1.
c. jika lebih besar,
proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi
tengah + 1.
tengah + 1.
4.
ulangi langkah 2 sampai data ditemukan, atau tidak ditemukan.
5.
Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih
besar dari pada
posisi akhir. Jika posisi awal sudah lebih besar daripada posisi akhir berarti data tidak ditemukan.
posisi akhir. Jika posisi awal sudah lebih besar daripada posisi akhir berarti data tidak ditemukan.
Ilustrasi atau Contoh
Pencarian Biner (Binary Search)
Misalkan kita ingin
mencari angka 14 pada sekumpulan data urut berikut :
Jawab :
1. mula-mula dicari data tengah, dengan rumus tengah = (awal+akhir) div 2 = (1+9) div 2 = 5, \
berarti data tengah adalah data ke-5, dengan nilai 13.
2.
data yang kita cari adalah 14, bandingkan nilai 14 dengan data tengah.
3.
karena 14 > 13, berarti proses dilanjutkan tetapi posisi awal dianggap sama
dengan posisi
tengah+1 atau 6
4.
data tengah yang baru didapat dari rumus (6+9) div 2 = 7, berarti data tengah yang
baru adalah data ke-7, yaitu 20.
5.
data yang kita cari adalah 14, bandingkan nilai 14 dengan nilai tengah.
6.
karena 14 < 20, berarti proses dilanjutkan, tetapi posisi akhir dianggap
sama dengan posisi
tengah-1 atau 6
tengah-1 atau 6
7. data tengah yang baru didapat dari rumus (6+6) div 2 = 6, berarti data tengah yang baru adalah
data ke-6, yaitu 14.
8.
data yang kita cari adalah 14, bandingkan dengan data tengah, ternyata sama.
9.
jadi data yang ditemukan pada indeks ke-6.
Bagaimana jika data
yang dicari tidak ditemukan, misalnya data yang dicari 16? Pencarian biner ini
akan berakhir jika data ditemukan atau posisi awal lebih besar dari pada posisi
akhir. Jika posisi awal sudah lebih besar daripada posisi akhir berarti data tidak
ditemukan.
Secara umum algoritma pencarian biner, adalah sebagai berikut :
(Data diurutkan lebih dahulu, data disimpan di data array, x adalah nilai yang dicari)
1. awal = 1.
2.
akhir = N.
3.
ketemu = false
4.
selama (awal<=akhir) dan (not ketemu) kerjakan baris 5 sampai 8.
5.
tengah = (awal+akhir) div 2
6. jika
(data [tengah] = x) maka ketemu = True
7. jika (x
< data [tengah] ) maka akhir ß tengah-l
8. jika (x
> data [tengah] maka awal ß tengah+1.
9. if (ketemu)
maka tengah adalah indeks dari data yang dicari, jika tidak data tidak
ditemukanContoh Program:
|
#include
<iostream>
#include
<conio.h>
int
binary_s(int array[], int size, int elemen);
int main()
{
int
size=10;
int data[10]={2, 3, 5, 6, 12, 44, 56, 65, 73 ,81} ;
cout<<"Data
Array"<<endl;
int i;
for(i=0;i<size;i++)
cout<<data[i]<<"
";
cout<<endl<<endl<<"masukkan
data yang ingin anda cari: ";
int cari;
cin>>cari;
// pencarian
int hasil;
hasil = binary_s(data, size, cari);
if (hasil==0)
cout<<"Nilai tidak ditemukan";
else
cout<<"Nilai
ditemukan";
getch();
}
int
binary_s(int array[], int size, int elemen)
{
int awal =
0;
int akhir =
size-1;
int
nilaiTengah = (awal+akhir)/2;
while
(nilaiTengah<=size && awal<=akhir)
{
nilaiTengah
= (awal+akhir)/2;
if
(array[nilaiTengah]==elemen)
return 1;
else if
(elemen<array[nilaiTengah])
akhir =
nilaiTengah-1;
else
awal =
nilaiTengah+1;
}
return 0;
|
Di bawah ini merupakan fungsi untuk
mencari data menggunakan pencarian biner.
|
int BinarySearch(int x)
{ int L = 0, R = Max-1, m; bool ditemukan = false; while((L <= R) && (!ditemukan)) { m = (L + R) / 2; if(Data[m] == x) ditemukan = true; else if (x < data[m]) R = m - 1; else L = m + 1; } if(ditemukan) return m; else return -1; } |
Fungsi diatas akan mengembalikan indeks dari data yang
dicari. Apabila data tidak ditemukan maka fungsi diatas akan mengembalikan
nilai –1. Jumlah pembandingan minimum pada pencarian biner adalah 1 kali, yaitu
apabila data yang dicari tepat berada di tengah-tengah. Jumlah pembandingan
maksimum yang dilakukan dengan pencarian biner dapat dicari menggunakan rumus
logaritma, yaitu: C = 2log(N)
LISTING PROGRAM
HASIL RUNNING
PENJELASAN
|
BARIS
|
PENJELASAN
|
|
1
|
header
#include <iostream> Untuk mengaktifkan keyword Input/Output (I/O)
yaitu cin (Input) dan cout (Output).
|
|
2
|
Merupakan File Header yang berfungsi
untuk menampilkan hasil antarmuka kepada pengguna.
|
|
4
|
Pengganti std::cout atau std::cin
|
|
6
|
Fungsi inisialisasi Untuk pencarian sebuah
data
|
|
7 dan 23
|
Awal dan akhir fungsi int BinarySearch
|
|
8
|
Pendeklarasian untuk data sebelah kiri
int L = 0, dan data sebelah kanan R = n-1, ketemu = 0;
|
|
9
|
Sebagai Perulangan menggunakan While dengan (L<=R) &&
(!ketemu)
|
|
10 dan 18
|
Awal dan akhiran dari perulangan Array
|
|
11
|
Proses perhitungan pencarian data
|
|
12
|
Penyeleksian kondisi pertama untuk
proses pencarian data jika data itu benar maka if(data[m]==x)
|
|
13
|
Proses dari penyeleksian kondisi
ketemu=!ketemu
|
|
14
|
Penyeleksian kondisi kedua untuk proses
pencarian data (x<Data[m])
|
|
15
|
Proses dari penyeleksian kondisi R=m-1
|
|
16
|
Penyeleksian kondisi apabila tidak
memenuhi penyeleksian kondisi sebelumnya
|
|
17
|
Penyeleksian kondisi , L=m+1
|
|
19
|
Penyeleksian kondisi apabila menemukan
data yang dicari
|
|
20
|
Proses pencarian data apabila data
ketemu maka m+1
|
|
21
|
Penyeleksian kondisi juka tidak
ditemukan data yang dicari
|
|
22
|
Proses pencarian data apabila data tidak
ketemu maka -1 atau salah
|
|
25
|
Fungsi dari main digunakan untuk
dijalankan terlebih dahulu
|
Flowchart
DAFTAR PUSTAKA
https://www.academia.edu/9216301/MAKALAH_BINARY_SEARCH
Tidak ada komentar:
Posting Komentar