Searching Binary Search
A.
Pengertian
Searching
Searching
adalah metode pencarian informasi dalam
suatu aplikasi, dengan suatu kunci (key).
Pencarian diperlukan untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari informasi tersebut
sebelumnya tidak diketahui. Pencarian selalu dinyatakan dengan referensi pada
adanya sekelompok data yang tersimpan secara terorganisasi, kelompok data
tersebut kita sebut table. Pada metode searching
(pencarian) ada 2 teknik yang digunakan yaitu:
1.
Pencarian sekuensial (sequential search) dan
2.
Pencarian biner (Binary search).
B.
Pengertian
Binary Search
Binary
search adalah algoritma pencarian untuk data
yang terurut. Pencarian dilakukan dengan cara menebak apakah data yang dicari
berada ditengah-tengah data, kemudian membandingkan data yang dicari dengan
data yang ada ditengah. Bila data yang ditengah sama dengan data yang dicari,
berarti data ditemukan. Namun, bila data yang ditengah lebih besar dari data
yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan berada
disebelah kiri dari data tengah dan data disebelah kanan data tengah dapat
diabai. Upper bound dari bagian data kiri yang baru adalah indeks dari
data tengah itu sendiri. Sebaliknya, bila data yang ditengah lebih kecil dari data
yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan besar
berada disebelah kanan dari data tengah. Lower bound dari data disebelah
kanan dari data tengah adalah indeks dari data tengah itu sendiri ditambah 1.
Demikian seterusnya.
Merupakan salah satu metode pencarian yang
menangani kasus terburuk (worst case)
pada pencarian secara berurutan. Proses pencarian binary search hanya dapat dilakukan pada data yang sudah berurutan.
Cara pencarian binary ini adalah dengan membagi dua elemen penampung nilai dan
membandingkan nilainya Algoritma dari binary
search adalah:
1.
Tentukan posisi awal = 0 dan posisi akhir = N
– 1
2.
Hitung posisi tengah = (posisi awal + posisi
akhir) / 2
3.
Bandingkan data yang dicari dengan elemen
posisi tengah
a)
Jika data yang dicari sama maka catat posisi
dan cetak kemudian berhenti
b)
Jika lebih besar maka akan dilakukan pencarian
kembali ke bagian kiri dengan nilai posisi awal = posisi tengah + 1 dan posisi
akhir tetap kemudian ulangi mulai poin 2
c)
Jika nilai datanya lebih kecil maka akan
dilakukan pencarian kembali ke bagian kiri dengan nilai posisi awal tetap dan
nilai posisi akhir = posisi tengah – 1 kemudian ulangi mulai poin 2.
C. Algoritma Binary
|
awal=0;
akhir=n-1;
do
{
tengah=(awal+akhir)/2;
if (x<data[tengah])
{
akhir=tengah-1;
}
else
{
awal=akhir+1;
}
}
while
(akhir>=awal)&&(data[tengah!=x]);
if(data[tengah]==x)
{
cout
<<"data "<<x<<" pada
posisi"<<tengah+1;
}
else
{
cout<<"data
tidak ditemukan";
}
|
Contoh:
|
#include<iostream>
#include<conio.h>
using namespace std;
int binarysearch(int Data[], int x,
int n)
{
int L=0, R=n-1,m,ketemu=0;
while ((L<=R)&&(!ketemu))
{
m=(L+R)/2;
if (Data[m]==x)
ketemu=!ketemu;
else if (x<Data[m])
R=m-1;
else
L=m+1;
}
if(ketemu)
return m+1;
else
return-1;
}
int main()
{
int Data[]={1,2,3,4,5,6,7,8,9,10};
int n=sizeof(Data);
cout <<endl;
int cari;
cout << "\tMasukkan data yang dicari :
";cin>>cari;
int ketemu=binarysearch(Data, cari, n);
if (ketemu>0)
cout << "\tData ditemukan
diposisi : "<<ketemu;
else
cout << "\t===Data Tidak
Ditemukan===";
getch();
}
|
Hasil running:
D. Pengertian Flowchart
Flowchart bukanlah merupakan sebuah kerangaka berpikir
seperti algoritma ataupun pseudocode flowchart pada dasarnya merupakan sebuah
bentuk gambar ataupun diagram yang memiliki aliran satu atau dua arah yang
berlaku secara sekuensial atau berkesinambungan. Fungsi utama dari flowchart
ini adalah untuk menggambarkan sebuah desain program dan untuk
merepresentasikan sebuah program atau sistem yang akan kita buat, berdasarkan
pola berpikir kita (berdasarkan algoritma).
E.
Unsur – unsur atau komponen yang terdapat pada flowchart
Secara
umum, dan secara garis besar, flowchart menerapkan unsur atau komponen yang
sama seperti komponen pada pemrograman. Berikut ini adalah beberapa unsur dalam
flowchart tersebut :
1. Input
2. Percabangan (biasanya menggunakan
command if dan switch)
3. Perulangan (biasanya menggunakan
command atau kode while, for, each, loop)
4. Output
Flowchart
dibuat sesuai dengan algoritma yang sudah disusun, dan kemudian dibuat sesuai
dengan urutan, perintah, serta ketentuan-ketentuan lainnya, yang dilambangkan
dengan symbol-symbol tertentu.
F.
Jenis Jenis Flowchart / Bagan Alir
a. System Flowchart
System flowchart dapat didefinisikan
sebagai bagan yang menunjukkan arus pekerjaan secara keseluruhan dari sistem.
Bagan ini menjelaskan urut-urutan dari prosedur-prosedur yang ada di dalam
sistem. Bagan alir sistem menunjukkan apa yang dikerjakan di sistem.
b. Document Flowchart
Bagan alir dokumen
(document flowchart) atau disebut juga bagan alir formulir (form
flowchart) atau paperwork flowchart merupakan bagan alir yang
menunjukkan arus dari laporan dan formulir termasuk tembusan-tembusannya.
c. Schematic Flowchart
Bagan alir skematik (schematic
flowchart) merupakan bagan alir yang mirip dengan bagan alir sistem, yaitu
untuk menggambarkan prosedur di dalam sistem. Perbedaannya adalah, bagan alir
skematik selain menggunakan simbol-simbol bagan alir sistem, juga menggunakan
gambar-gambar komputer dan peralatan lainnya yang digunakan. Maksud penggunaan
gambar-gambar ini adalah untuk memudahkan komunikasi kepada orang yang kurang
paham dengan simbol-simbol bagan alir. Penggunaan gambar-gambar ini
memudahkan untuk dipahami, tetapi sulit dan lama menggambarnya.
d. Program Flowchart
Bagan alir program (program flowchart)
merupakan bagan yang menjelaskan secara rinci langkah-langkah dari proses
program. Bagan alir program dibuat dari derivikasi bagan alir sistem.
Bagan alir program dapat terdiri dari dua macam, yaitu bagan
alir logika program (program logic flowchart) dan bagan alir
program komputer terinci (detailed computer program flowchart).
Bagan alir logika program digunakan untuk menggambarkan tiap-tiap langkah di
dalam program komputer secara logika. Bagan alat- logika program ini
dipersiapkan oleh analis sistem. Gambar berikut menunjukkan bagan alir logika
program. Bagan alir program komputer
terinci (detailed computer program flow-chart) digunakan untuk
menggambarkan instruksi-instruksi program komputer secara terinci. Bagan
alir ini dipersiapkan oleh pemrogram.
e. Process Flowchart
Bagan alir proses (process
flowchart) merupakan bagan alir yang banyak digunakan di teknik
industri. Bagan alir ini juga berguna bagi analis sistem untuk menggambarkan
proses dalam suatu prosedur.
G.
Simbol - Simbol Flowchart / Bagan Alir
Komentar
Posting Komentar