METODE SEARCHING (Sequential Search & Binary Search) dalam C++
METODE SEARCHING (Sequential Search & Binary Search)
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 :
Pencarian sekuensial (sequential search) dan Pencarian biner (Binary
search).
1. Pencarian sekuensial (sequential search)
Pencarian
sekuensial (sequential search) atau sering disebut pencarian linier
menggunakan prinsip sebagai berikut : data yang ada di bandingkan satu
persatu secara berurutan dengan yang dicari.
Pada
dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai
dengan jumlah data. Pada setiap perulangan , di bandingkan data ke-i
dengan yang dicari. Apabila sama , berarti data telah ditemukan .
Sebaliknya apabila sampai akhir pengulangan , tidak ada yang sama
berarti data tidak ada.
a. Sekuensial versi berdampingan dengan sintak C:
Contoh listing fungsi dalam bahasa C++ :
Int SequensialSearch(List_type list, Key_type target)
{ int location; // penempatan data
for (location=0;location
if (EQ(list.entry[location].key,target))
return location;
return –1
b. Sekuensial versi berangkai dengan sintak C:
Node_type* SequentialSearch (List_type list, Key_type target)
{ Node_type* location;
for (location=list.head;location!=NULL;locatioan->next)
if(EQ(location->info.key,target))
return location;
return NULL
}
Pengimplementasian sintak sekuensial search pada bahasa C :
#include
#include
void main()
{
clrscr();
int data[8] = {3,9,7,-3,11,5,2,18};
int cari,index;
int ketemu=0;
cout<<"Inputkan data yang ingin di cari = ";
cin>>cari;
for(int i=0;i<8;i++)
{
if(data[i] == cari)
{
ketemu=1;
index=1;
break;
}
}
if(ketemu == 1)
{
cout<<"Data tersedia!"<
cout<<"Data Terletak di index ke - "<
}
else cout<<"Data tidak tersedia!"<
getch();
}
2. Pencarian Biner (Binary Search)
Salah
satu syarat pencarian biner (binary search) dapat dilakukan adalah data
sudah dalam keadaan terurut. Dengan kata lain, apabila data belum dalam
keadaan terurut , pencarian biner tidak dapat dilakukan . Dalam
kehidupan sehari-hari, sebenarnya kita juga serig menggunakan pencarian
biner. Misalnya saat kita ingin mencari suatu kata dalam kamus.
Langkah dalam pencarian biner adalah :
1. Mula-mula diambil dari 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 di cari 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.
4. Ulangi langkah kedua hingga data ditemukan , atau tidak ditemukan.
5. Pencarian
biner ini akan berakhir jika data ditemukan posisi awal lebih besar
dari pada posisi akhir. Jika posisi awal sudah lebih besar dari posisis
akhir berarti data tidak diketemukan.
Contoh sintak Binary search pada bahasa C:
#include
#include
int data[10] = {1,4,6,8,18,23,35,49,60,75};
int binary_search(int cari)
{
int l,r,m;
int n = 10;
l = 0;
r = n-1;
int ketemu = 0;
while(l<=r && ketemu==0)
{
m = (l+r)/2;
if ( data[m] == cari )
ketemu = 1;
else
if (cari <>
r = m-1;
else l = m+1;
}
if(ketemu == 1) return 1; else return 0;
}
void main()
{
clrscr();
int cari,hasil;
cout<<"Masukan data yang ingin dicari = ";
cin>>cari;
hasil = binary_search(cari);
if(hasil == 1)
{
cout<<"Data tersedia!"<
}
else
if(hasil == 0)cout<<"Data tidak tersedia!"<ETODE SEARCHING (Sequential Search & Binary Search) dalam C++
METODE SEARCHING (Sequential Search & Binary Search)
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 :
Pencarian sekuensial (sequential search) dan Pencarian biner (Binary
search).
1. Pencarian sekuensial (sequential search)
Pencarian
sekuensial (sequential search) atau sering disebut pencarian linier
menggunakan prinsip sebagai berikut : data yang ada di bandingkan satu
persatu secara berurutan dengan yang dicari.
Pada
dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai
dengan jumlah data. Pada setiap perulangan , di bandingkan data ke-i
dengan yang dicari. Apabila sama , berarti data telah ditemukan .
Sebaliknya apabila sampai akhir pengulangan , tidak ada yang sama
berarti data tidak ada.
a. Sekuensial versi berdampingan dengan sintak C:
Contoh listing fungsi dalam bahasa C++ :
Int SequensialSearch(List_type list, Key_type target)
{ int location; // penempatan data
for (location=0;location
if (EQ(list.entry[location].key,target))
return location;
return –1
b. Sekuensial versi berangkai dengan sintak C:
Node_type* SequentialSearch (List_type list, Key_type target)
{ Node_type* location;
for (location=list.head;location!=NULL;locatioan->next)
if(EQ(location->info.key,target))
return location;
return NULL
}
Pengimplementasian sintak sekuensial search pada bahasa C :
#include
#include
void main()
{
clrscr();
int data[8] = {3,9,7,-3,11,5,2,18};
int cari,index;
int ketemu=0;
cout<<"Inputkan data yang ingin di cari = ";
cin>>cari;
for(int i=0;i<8;i++)
{
if(data[i] == cari)
{
ketemu=1;
index=1;
break;
}
}
if(ketemu == 1)
{
cout<<"Data tersedia!"<
cout<<"Data Terletak di index ke - "<
}
else cout<<"Data tidak tersedia!"<
getch();
}
2. Pencarian Biner (Binary Search)
Salah
satu syarat pencarian biner (binary search) dapat dilakukan adalah data
sudah dalam keadaan terurut. Dengan kata lain, apabila data belum dalam
keadaan terurut , pencarian biner tidak dapat dilakukan . Dalam
kehidupan sehari-hari, sebenarnya kita juga serig menggunakan pencarian
biner. Misalnya saat kita ingin mencari suatu kata dalam kamus.
Langkah dalam pencarian biner adalah :
1. Mula-mula diambil dari 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 di cari 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.
4. Ulangi langkah kedua hingga data ditemukan , atau tidak ditemukan.
5. Pencarian
biner ini akan berakhir jika data ditemukan posisi awal lebih besar
dari pada posisi akhir. Jika posisi awal sudah lebih besar dari posisis
akhir berarti data tidak diketemukan.
Contoh sintak Binary search pada bahasa C:
#include
#include
int data[10] = {1,4,6,8,18,23,35,49,60,75};
int binary_search(int cari)
{
int l,r,m;
int n = 10;
l = 0;
r = n-1;
int ketemu = 0;
while(l<=r && ketemu==0)
{
m = (l+r)/2;
if ( data[m] == cari )
ketemu = 1;
else
if (cari <>
r = m-1;
else l = m+1;
}
if(ketemu == 1) return 1; else return 0;
}
void main()
{
clrscr();
int cari,hasil;
cout<<"Masukan data yang ingin dicari = ";
cin>>cari;
hasil = binary_search(cari);
if(hasil == 1)
{
cout<<"Data tersedia!"<
}
else
if(hasil == 0)
cout<<"Data tidak tersedia!"<
getch();
}
· Pencarian Sekuensial :
a. Kelebihannya :
- Relatif lebih cepat dan efisien untuk data yang terbatas
- Algoritma sederhana
b. Kekuranganya :
- Kurang cepat untuk data dalam jumlah besar
- Beban komputasi cenderung lebih besar
· Pencarian Biner :
a. Kelebihannya :
- Untuk data dalam jumlah besar, waktu searching lebih cepat
- Beban komputasi lebih kecil
b. Kekuranganya :
- Data harus sudah di-sorting lebih dulu ( dalam keadaan terurut ) - See more at: http://edyuty.blogspot.com/2013/05/metode-searching-sequential-search.html#sthash.9kJZxAzl.dpuf
getch();
}
· Pencarian Sekuensial :
a. Kelebihannya :
- Relatif lebih cepat dan efisien untuk data yang terbatas
- Algoritma sederhana
b. Kekuranganya :
- Kurang cepat untuk data dalam jumlah besar
- Beban komputasi cenderung lebih besar
· Pencarian Biner :
a. Kelebihannya :
- Untuk data dalam jumlah besar, waktu searching lebih cepat
- Beban komputasi lebih kecil
b. Kekuranganya :
- Data harus sudah di-sorting lebih dulu ( dalam keadaan terurut ) - See more at: http://edyuty.blogspot.com/2013/05/metode-searching-sequential-search.html#sthash.9kJZxAzl.dpuf
BRANCH
AND BOUND
•
Metode Branch and Bound adalah sebuah teknik
algoritma yang secara khusus mempelajari bagaimana caranya memperkecil Search
Tree menjadi sekecil mungkin.
•
Sesuai dengan namanya, metode ini terdiri dari 2
langkah yaitu :
–
Branch yang artinya membangun semua cabang tree
yang mungkin menuju solusi.
–
Bound
yang artinya menghitung node mana yang merupakan active node (E-node) dan node
mana yang merupakan dead node (D-node) dengan menggunakan syarat batas
constraint (kendala).
TEKNIK BRANCH AND BOUND
•
FIFO Branch and Bound
–
Adalah teknik Branch and Bound yang menggunakan
bantuan queue untuk perhitungan Branch and Bound secara First In First Out.
•
LIFO Branch and Bound
–
Adalah teknik Branch and Bound yang menggunakan
bantuan stack untuk perhitungan Branch and Bound secara Last In First Out.
•
Least Cost Branch and Bound
–
Teknik ini akan menghitung cost setiap node.
Node yang memiliki cost paling kecil dikatakan memiliki kemungkinan paling
besar menuju solusi.
MASALAH YANG DAPAT DIPECAHKAN
•
Branch and Bound dapat digunakan untuk
memecahkan berbagai masalah yang menggunakan Search Tree
–
Traveling Salesman Problem
–
N-Queen Problem
–
15 Puzzle Problem
–
0/1 Knapsack Problem
-Shortest Path
Algoritma
Brute Force
Algoritma Brute Force
adalah sebuah pendekatan
yang lempang (straightforward) untuk memecahkan
suatu masalah, biasanya didasarkan pada pernyataan
masalah (problem statement) dan definisi konsep
yang dilibatkan.[7]
Prinsip – prinsip
algoritma brute force untuk
menyelesaikan persoalan Integer Knapsack ialah:
1) Mengenumerasikan
semua himpunan bagian
dari solusi.
2) Mengevaluasi total
keuntungan dari setiap
himpunan bagian dari langkah pertama
3) Pilih himpunan
bagian yang mempunyai total
keuntungan terbesar
Algoritma
Greedy
Secara harfiah,
greedy berarti rakus atau tamak.
Algoritma Greedy merupakan
algoritma sedarhana
dan lempang yang paling populer untuk pemecahan
persoalan optimasi
(maksimum atau minimum).
Prinsip greedy adalah: “take what you can
get
now!”, yang digunakan dalam konteks positif.[7]
Ada tiga pendekatan dalam
menyelesaikan
persoalan Integer
Knapsack dengan algoritma
Greedy:
1) Greedy by
profit.
Pada setiap langkah,
knapsack diisi dengan objek
yang mempunyai keuntungan terbesar. Strategi ini
mencoba memaksimumkan keuntungan dengan
memilih objek yang paling menguntungkan terlebih
dahulu.
2) Greedy by weight.
Pada setiap langkah,
knapsack diisi dengan objek
yang mempunyai berat paling
ringan. Strategi ini
mencoba memaksimumkan keuntungan dengan
memasukkan sebanyak mungkin objek ke dalam
knapsack.
3) Greedy by
density.
Pada setiap langkah,
knapsack diisi dengan objek
yang mempunyai densitas,
pi /wi terbesar.
Strategi
ini mencoba
memaksimumkan keuntungan dengan
memilih objek yang mempunyai keuntungan per unit
berat terbesar.
Algoritma Dynamic Programming
Program Dinamis (dynamic programming): metode
pemecahan masalah dengan cara menguraikan solusi
menjadi sekumpulan
langkah (step) atau tahapan
(stage) sedemikian
sehingga solusi dari persoalan
dapat dipandang dari
serangkaian keputusan yang
saling berkaitan.[7]
Pada penyelesaian persoalan dengan metode ini:
(1) terdapat sejumlah
berhingga pilihan yang
mungkin,
(2) solusi pada
setiap tahap dibangun dari hasil
solusi tahap sebelumnya,
(3) kita
menggunakan persyaratan optimasi dan
kendala untuk membatasi sejumlah pilihan yang
harus dipertimbangkan pada suatu tahap.
Dua pendekatan yang
digunakan dalam Dynamic
Progamming adalah
maju (forward atau up-down)
dan mundur (backward atau bottom-up).
Misalkan x1, x2, …, xn menyatakan peubah (variable)
keputusan yang harus
dibuat masing-masing untuk
tahap 1, 2, …, n. Maka,
a. Program
dinamis maju: Program dinamis
bergerak mulai dari tahap 1, terus maju ke tahap 2, 3, dan
seterusnya sampai tahap n. Runtunan
peubah keputusan adalah x1, x2, …, xn.
b. Program
dinamis mundur: Program dinamis
bergerak mulai dari tahap
n, terus mundur ke
tahap n – 1, n – 2, dan seterusnya sampai tahap
1. Runtunan peubah
keputusan adalah xn,
xn-1,
…, x1.
Secara umum, ada
empat langkah yang dilakukan
dalam mengembangkana
algoritma program
dinamis:
1. Karakteristikkan
struktur solusi optimal.
2. Definisikan secara
rekursif nilai solusi
optimal.
3. Hitung nilai
solusi optimal secara maju atau
mundur.
4. Konstruksi solusi
optimal.
Algoritma
Divide and Conquer
Algoritma divide and
conquer sudah lama diperkenalkan sebagai sumber dari
pengendalian proses paralel, karena masalah-masalah yang
terjadi dapat diatasi
secara independen. Banyak arsitektur dan bahasa pemrograman
paralel mendesain
implementasinya (aplikasi) dengan struktur dasar dari
algoritma divide and conquer.
Untuk menyelesaikan masalah-masalah yang besar, dan dibagi
(dipecah) menjadi
bagian yang lebih kecil dan menggunakan sebuah solusi untuk
menyelesaikan
problem awal adalah prinsip dasar dari pemrograman/strategi
divide and conquer.
Terima Kasih
Nama
: M.Ropianto, M.Kom
NIDN:
: 102867804
Status
: Dosen Tetap YAPISTA / STT Ibnu Sina
Pengampuh
Matakuliah
: Algoritma & Pemrograman 3
