BINARY
SEARCH
A.
ALGORITMA
BINARY SEARCH
awal=0;
akhir=n-1;
do
{
tengah=(awal+akhir)/2
if(x<data[tengah])
akhiir=tengah-1;
else
awal=tengah+1;
}
while((akhir<=awal)&&(data[tengah]!=x));
{
if(x==data[tengah])
cout<<”data “<<x<<” pada posisi
“<<tengah+1;
}
B. CONTOH PROGRAM BINARY SEARCH
a. Hasil
Listing Program
b. Hasil
Running Program
C.
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. Pada intinya, algoritma ini menggunakan prinsip
divide and conquer, dimana sebuah masalah atau tujuan diselesaikan dengan cara
mempartisi masalah menjadi bagian yang lebih kecil. Algoritma ini membagi
sebuah tabel menjadi dua dan memproses satu bagian dari tabel itu
saja.Algoritma ini bekerja dengan cara memilih record dengan indeks tengah dari
tabel dan membandingkannya dengan record yang hendak dicari.
Jika record tersebut
lebih rendah atau lebih tinggi, maka tabel tersebut dibagi dua dan bagian tabel
yang bersesuaian akan diproses kembali secara rekursif. 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.
1) Keunggulan
Keunggulan utama dari
algoritma binary search adalah kompleksitas algoritmanya yang lebih kecil
daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu
yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam
sebuah table, lebih kecil daripada waktu yang dibutuhkan algoritma sequential
search.
2) Kelemahan
Data harus disorting
dahulu dan algoritma lebih rumit, tidak baik untuk data berantai. algoritma ini
hanya bisa digunakan pada tabel yang elemennya sudah terurut baik menaik maupun
menurun.
3) Fungsi
Pencarian Biner (Binary Search) dilakukan
untuk :
a) 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.
b) 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).
c) Syarat
utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut,
misalkan terurut menaik.
d) Prinsip
dari pencarian biner dapat dijelaskan sebagai berikut :
1. Data
diambil dari posisi 1 sampai posisi akhir N
2. Kemudian
cari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2
3. Kemudian
data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau
lebih kecil, atau lebih besar?
4. Jika
lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi
tengah + 1
5. Jika
lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi
tengah – 1
6. Jika
data sama, berarti ketemu.
Daftar pustaka
https://www.academia.edu/9216301/MAKALAH_BINARY_SEARCH diakses
pada tanggal 19 april 2019 pukul 10.48 wita
Tidak ada komentar:
Posting Komentar