BINERY SERCHING
A. Pengertian Searching
Searching adalah
mencari data yang dibutuhkan. Searching
dalam pemrograman bisa dilakukan untuk mencari data yang ada di dalam memori
komputer. Dalam kehidupan sehari-hari kita juga sering melakukan kegiatan searching seperti mencari data atau informasi
yang ada dalam internet. Ada beberapa metode yang dapat digunakan untuk searching, ada yang dinamakan:
1. Sequential
Search
2. Binary Search
B. Binary 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) div 2
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.
c. jika lebih
besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah
+ 1.
d. ulangi
langkah 2 sampai data ditemukan, atau tidak ditemukan.
e. 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.
C. 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.
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)
(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 < tengah-lßdata [tengah] ) maka akhir
8.
jika (x > tengah+1.ßdata [tengah] maka awal
9.
if (ketemu) maka tengah adalah indeks dari data yang
dicari, jika tidak data tidak ditemukan
D. Algoritma Binary Search
awal=0, akhir=n-1;
do
{
tengah :
(awal+akhir)/2;
if
(x<data[tengah])
{
akhir
= tengah-1;
}
else
{
awal =
tengah+1;
}
}
while ((akhir>=awal) &&
(data[tengah]!=x))
if (data[tengah]==x)
{
cout<<"Data "<<x<<"Pada Posisi
"<<tengah+1;
}
else
{
cout<<"Data tidak Ditemukan"<<endl;
}
|
E. Contoh Program Binary Search
Dan ini
adalah hasil running dari pencarian nilai menggunakan metode binary search yang
data nilai nya dapat ditemukan
Dan ini
adalah hasil running dari pencarian nilai menggunakan metode binary search yang
data nilai nya tidak dapat ditemukan
SUMBER :
Tidak ada komentar:
Posting Komentar