SEARCHING
BINARY SEARCH
Disusun oleh :
Dian Kuuma Wardani
Teknik
Informatika Politeknik Banyuwangi
Jalan
Raya Jember KM 13 Labanasem, Kabat, Banyuwangi
KATA PENGANTAR
Puji syukur penulis penjatkan kehadirat Tuhan Yang Maha Esa,
atas rahmat-Nya maka penulis dapat menyelesaikan penyusunan makalah yang
berjudul “Seaching Binary Search”.
Penulisan makalah adalah merupakan salah satu tugas dan
persyaratan untuk menyelesaikan tugas mata Kuliah Logika dan Algoritma di
Politeknik Banyuwangi.
Dalam Penulisan makalah ini penulis merasa masih banyak
kekurangan-kekurangan baik pada teknis penulisan maupun materi, mengingat akan
kemampuan yang dimiliki penulis. Untuk itu kritik dan saran dari semua pihak
sangat penulis harapkan demi penyempurnaan pembuatan makalah ini.
Dalam penulisan makalah ini penulis menyampaikan ucapan
terima kasih yang tak terhingga kepada pihak-pihak yang membantu dalam
menyelesaikan penelitian ini, khususnya kepada Bp. Aulia El Hakim, S.ST selaku
dosen mata kuliah Logika dan Algoritma
Akhirnya penulis berharap semoga Tuhan memberikan imbalan
yang setimpal pada mereka yang telah memberikan bantuan, dan dapat menjadikan
semua bantuan ini sebagai ibadah, Amin Yaa Robbal ‘Alamin. Dan penulis pun
berharap agar makalah ini dapat memberikan manfaat bagi pembaca.
|
DAFTAR ISI
Halaman Judul………………………………………………………………………
Kata Pengantar………………………………………………………………….......i
Daftar Isi……………………………………………………………………….…...ii
BAB I PENDAHULUAN
1.1
Latar Belakang……………………………………………………...1
1.2
Runusan
Masalah…………………………………………………...2
1.3
Tujuan ……………………………………………………...............2
1.4
Manfaat……………………………………………………..............2
BAB II ISI
2.1
Konsep
dan Istilah…………………………………………………..3
2.2
Pengertian
Binary Search……………………………………….......3
2.3
Algoritma
dari Binary search……………………………………….4
2.4
Flowchart
dari Binary Search……………………………………….4
2.5
Coding Binary
Seacrh dan Running Program………………………6
2.6
Contoh
Soal Binary Search…………………………………………11
BAB III PENUTUP
3.1
Kesimpulan…………………………………………………..…….12
3.2
Saran………………………………………….................................12
DAFTAR PUSTAKA
BAB
I
PENDAHULUAN
1.1 Latar Belakang
Seiring
dengan berkembangnya Teknologi Informasi, yang membutuhkan kecepatan dan
ketepatan dalam berbagai aspek kehidupan. Kita dituntut untuk bergerak cepat
dalam segala hal, termasuk juga dalam bidang komunikasi informasi. Salah
satunya dalam bidang statistic yang meliputi pencarian data.
Keberadaan bahasa pemograman telah
menghadirkan nuansa tersendiri di lingkup dunia kerja, karena pekerjaan kita
pada saat ini selalu mengikuti kemajuan
teknologi. Demi menambah kepuasan masyarakat menjadi sisi yang paling
ditonjolkan. Hal ini
tentu saja semakin memantapkan posisinya sebagai bahasa penghantar antara manusia yang dapat dipahami, dan dapat dijalankan oleh seorang programmer.. Ia
telah menjadi bagian hidup masyarakat masa kini, bukan hanya sebagai sumber informasi, tetapi juga gaya hidup dan kebudayaan.
tentu saja semakin memantapkan posisinya sebagai bahasa penghantar antara manusia yang dapat dipahami, dan dapat dijalankan oleh seorang programmer.. Ia
telah menjadi bagian hidup masyarakat masa kini, bukan hanya sebagai sumber informasi, tetapi juga gaya hidup dan kebudayaan.
Sehingga
banyak progamer yang membuat program yang mempermudah kerja dalam bidang statistika
dan informasi, yakni dalam hal pencarian data. Dari program pencarian data terdapat
algoritma-algoritma yang digunakan untuk mencari sebuah data, salah satunya
adalah binary search.
Adapun
Kelebihan dari Searching dengan
metode Binary Sort adalah Untuk Pencarian data yang jumlahnya banyak, waktu
pencarian relatif cepat. selain itu beban komputasi juga lebih kecil karena
pencarian dilakukan dari depan, belakang, dan tengah. Sehingga metode pencarian
dengan menggunakan binary sort banyak digunakan.
Sehingga pada makalah ini kami
melmilih metode pencarian dengan Binary sort, karena melihat keunggulan yang
dimiliki oleh binary sort. Selain itu ketelitian pencarian binary sort sangat
akurat.
1.2 Rumusan Masalah
-
Bagaimana cara mencari data dengan cepat
dan ukurat?
1.3
Tujuan
-
Mempermudah
pekerjaan manusia dalam bidang Informasi.
- Mempermudah pekerjaan
manusia dalam bidang Statistik.
- Mempermudah pekerjaan
manusia dalam bidang komputerisasi lainya terutama dalam bidang pencarian data.
1.4
Manfaat
-
Pekerjaan
manusia dalam bidang teknologi jadi lebih mudah, cepat, dan efisien waktu.
BAB
II
ISI
2.1
Konsep dan Istilah
Sebelum belajar
binary search kita harus mempelajari istilah yang banyak ditemui dalammateri
ini. Seperti misalnya :
-
Internal Search : Algoritma pencarian
yang dilakukan dalam main memory computer
-
External search : Algoritma pencarian
yang melibatkan external media menambah main memory
-
Key : Sebuah subset dari isi sebuah data
yang digunakan untuk perbandingan selama proses pencarian
-
Big-O Nation-Notasi yang digunakan untuk
mengindikasikan kenaikan (order of growth) unjuk kerja dari sebuah algoritma
searching
2.2
Pengertian Binary Search
Sebuah algoritma pencarian biner (atau pemilahan biner)
adalah sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (array)
linear, dengan menghilangkan setengah data pada setiap langkah, dipakai secara
luas tetapi tidak secara ekslusif dalam ilmu komputer. Sebuah pencarian biner
mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan
apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah
sisanya dengan cara yang sama. Sebuah pencarian biner adalah salah satu contoh
dari algoritma divide and conquer (atau lebih khusus algoritma decrease and
conquer) dan sebuah pencarian dikotomi (lebih rinci di Algoritma pencarian).
Penerapan terbanyak dari pencarian biner adalah untuk
mencari sebuah nilai tertentu dalam sebuah list terurut. Jika dibayangkan,
pencarian biner dapat dilihat sebagai sebuah permainan tebak-tebakan, kita
menebak sebuah bilangan, atau nomor tempat, dari daftar (list) nilai.
Pencarian diawali dengan memeriksa nilai yang ada pada
posisi tengah list; oleh karena nilai-nilainya terurut, kita mengetahui apakah
nilai terletak sebelum atau sesudah nilai yang di tengah tersebut, dan
pencarian selanjutnya dilakukan terhadap setengah bagian dengan cara yang sama.
Metoda Pencarian Biner ( Binary
Search) hanya bisa diterapkan jika data array sudah terurut. pengurutan Array bisa menggunakan
jenis sorting descending atau asscending. Kelebihan dari Searching dengan
metode Binary Sort adalah Untuk Pencarian data yang jumlahnya banyak, waktu
pencarian relatif cepat. selain itu beban komputasi juga lebih kecil karena
pencarian dilakukan dari depan, belakang, dan tengah. namun ada pula
kekurangannya, yaitu data harus disorting dahulu dan Algoritma lebih rumit,
tidak baik untuk data berangkai.
Pencarian
Biner (Binary Search) dilakukan untuk :
- Memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.
- Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).
- Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik
2.3 Algoritma dari Binary Search
Proses
yang terjadi pada pencarian dengan metode ini adalah sebagai berikut :
- Membaca Array data
- Apabila Array belum terurut maka array diurutkan terlebih dahulu.
- Menentukan data yang akan dicari
- Menentukan elemen tengah dari array
- Jika nilai elemen tengah sama dengan data yang dicari, maka pencarian berhenti.
- Jika elemen tengah tidak sama dengan data yang dicari maka :
- Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
- Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.
2.4 Flowchart dari Binary Search
2.5 Coding Binary Search
#include
<stdio.h>
int main()
{
int a[20]
= {0};
int n, i,
j, temp;
int *beg,
*end, *mid, target;
printf("
Masukan banyak data(banyak data jangan sampai data ke 20):\n");
scanf("%d",
&n);
if (n
>= 20) return 0; // ouch!
printf("
Masukan Nilai data Array:\n" );
for(i = 0;
i < n; i++)
{
scanf("%d",
&a[i]);
}
// sort
the loaded array, a must for binary search!
// you can
apply qsort or other algorithms here
for(i = 0;
i < n-1; i++)
{
for(j = 0;
j < n-i-1; j++)
{
if (a[j+1]
< a[j])
{
temp =
a[j];
a[j] =
a[j+1];
a[j+1] =
temp;
}
}
}
printf("
urutan data:");
for(i = 0;
i < n; i++)
{
printf("%d
", a[i]);
}
// point
to beginning and end of the array
beg =
&a[0];
end =
&a[n]; // use n = one element past the loaded array!
printf("\n
Poin awal %d Poin akhir to %d",beg, end); // test
// mid
should point somewhere in the middle of these addresses
mid = beg
+= n/2;
printf("\n
data tengah %d", mid); // test
printf("\n
masukan data yang dicari:");
scanf("%d",&target);
// binary
search, there is an AND in the middle of while()!!!
while((beg
<= end) && (*mid != target))
{
// is the
target in lower or upper half?
if (target
< *mid)
{
end = mid -
1; // new end
n = n/2;
mid = beg
+= n/2; // new middle
}
else
{
beg = mid
+ 1; // new beginning
n = n/2;
mid = beg
+= n/2; // new middle
}
}
// did you
find the target?
if (*mid
== target)
{
printf("\n
%d data ditemukan!", target);
}
else
{
printf("\n
%d not found!", target);
}
getchar();
// trap enter
getchar();
// wait
return 0;
}
Progam setelah running
2.6 Contoh Soal Binary Search
Misalnya
data yang dicari 17
•
0 1 2 3 4 5 6 7 8
•
3 9 11 12 15 17 23 31 35
•
A B C
•
Karena
17 > 15 (data tengah), maka: awal = tengah + 1
•
0 1 2 3 4 5 6 7 8
•
3 9 11 12 15 17 23 31 35
•
A B C
•
Karena
17 < 23 (data tengah), maka: akhir = tengah – 1
•
0 1 2 3 4 5 6 7 8
•
3 9 11 12 15 17 23 31 35
•
A=B=C
•
Karena
17 = 17 (data tengah), maka KETEMU!
BAB
III
PENUTUP
Puji syukur penulis sampaikan kepada
tuhan Yang MahaEsa, Karena Atas berkatdan rahmatnya kami dapat menyelesaikan
makalah ini. Kemudian ucapan terimakasih kamisampaikan kepada kedua orangtua kamiyang
senantiasa memberiakan dukungan moral maupun materi. Dan kami juga sampaikan
banyak terimahkasih kepada bapak Aulia El Hakim, S.ST selaku Dosen Logika dan
Algotirma karena telah memberikan banyak bimbingan pada kami.
Semoga makalah ini memiliki banyak
manfaat bagi para pembaca.
3.1
Kesimpulan
Adapun
kesimpulan yang dapat ditarik dari makalah Searching binary search ini adalah
kita dapat mempermudah pekerjaan manusia dalam bidang Informasi, mempermudah
pekerjaan manusia dalam bidang Staristik, mempermudah pekerjaan manusia dalam
bidang komputerisasi lainya terutama dalam bidang pencarian data.
Dengan binary search ini kita dapat
mempermudah pekerjaan manusia di dalam hal mencari sebuah data. Sehingga dapat
menciptakan suatu progam yang bermanfaat dan memiliki nilaiekonomi.
3.2 Saran
-
Telitilah dalam menghitung binary code
-
Telitilah dalam menghitung nilai tengah dari binary code
-
Dan yang terpenting teelitilah dalam memasukan bahasa pemograman pada saat
mengcompile(ngoding).
DAFTAR PUSTAKA
Posted by Atmaja Dharma,
“Binary Search”dharmaatmaja.wordpress.com
(June 29, 2009)
Posted by Pengertian
Binary Search / Pencarian Biner” Sumber
wikipedia.org (March 20, 2010)
Posted by Rachmat Antonius C, S.Kom, “Struktur Data (2) Searching Array” goole.co.id(03
September 2010)
Posted by Boys Cute, “BAB VII Pencarian Data Searching” goole.co.id(09
May 2011)
Posted by Hndsanjaya, “Algoritma Sorting & Searching C++”wikipedia.org(4 July 2010 at 22:08)
Posted by Entin@Nanarm,
“Searching Sequential and Binary search”goole.co.id(13
August 2009)
SEMOGA BERMANFAAT!!!!!!
