Selamat
pagi kali ini saya akan memberikan sedikit pemahaman tentang bagaimana
algoritma atau logikanya dalam melakukan searching. Teknik ini dapat di gunakan
di bahasa pemrograman apapun. Karena rata-rata semua searching
logikanya seperti ini dan yang membedakan hanya sintak penulisannya
saja. Langsung saja di baca dan di pahami penjelasan dari saya ini.
Teknik Searching
Proses
pencarian --> menemukan harga/data tertentu didalam sekumpulan
harga yang bertipe sama. Dalam proses pemrograman serching/pencarian biasanya
digunakan untuk
a. proses update atau penghapusan
data à sebelumnya melakukan proses pencarian data.
b. Penyisipan data pada sekumpulan
data, jika data sudah ada maka proses penyisipan tidak diperkenankan. Jika data
tidak ada maka proses penyisipan dilakukan àtujuan digunakan agar tidak
terjadi duplikasi data
1. Tehnik Pencarian
Tunggal :
a.
Tehnik
Sequential Search / Linier Search
b.
Tehnik
Binary Search
2. Tehnik Pencarian Nilai
MAXMIN :
a.
Tehnik
StaritMAXMIN
b.
Tehnik
D and C
A. Teknik
Sequential.
Pencarian
Sekuensial (sequential searching) atau pencarian berurutan
sering disebut pencarian linear merupakan metode pencarian yang paling
sederhana. Pencarian beruntun adalah proses membandingkan setiap elemen
larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen
yang dicari ditemukan atau seluruh elemen sudah diperiksa.
Algoritma/Caranya:
Pencarian berurutan menggunakan prinsip sebagai
berikut :
1. data yang ada dibandingkan satu
per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan
atau tidak ditemukan.
2. Pada dasarnya, pencarian ini
hanya melakukan pengulangan dari 1 sampai dengan jumlah data.
3. Pada setiap pengulangan,
dibandingkan data ke-i dengan yang dicari.
4. Apabila sama, berarti data telah
ditemukan. Sebaliknya apabila sampai akhir pengulangan tidak ada data yang
sama, berarti data tidak ada.
CONTOH KASUS
:
Array :
int a [5] = {3,5,4,9,1} (index array padabahasa C++
dimulaidari index ke 0 !!!) jika kita ingin mencari bilangan 4 dalam array
tersebut, maka proses yang terjadi kita mencari
1. dari array index ke-0, yaitu 3,
dicocokan dengan bilangan yang akan dicari, jika tidak sama, maka mencari ke
index berikutnya
2. pada array index ke-1, juga bukan
bilangan yang dicari, maka kita mencari lagi pada index berikutnya
3. pada array index ke-2, ternyata
bilangan yang kita cari ada ditemukan, maka kita keluar dari looping pencarian.
B. Teknik
Binary Search.
Binary Search adalah algoritma pencarian untuk data yang telah terurut, yaitu
data yang diurutkan dari yang besar ke kecil ataupun sebaliknya, pencarian
dilakukan dengan langsung menebak apakah data yang dicari berada
ditengah-tengah data yang lainnya, kemudian membandingankan data yang ditengah
dengan data yang dicari, apabila sama maka dapat dikatakan data ditemukan,
namun apabila data yang dicari ternyata lebih kecil daripada elemen tengah,
maka pencarian dilakukan dari bagian tengah ke bawah.
Algoritma/Caranya
:
1. Anggap saja Urutan Terendah (UR) = 1, Urutan
Tertinggi (UT) = N (nilai belum diketahui, bisa 10,100, atau 1000).
2. Ketika Urutam Tertinggi (UT) tidak lebih besar daripada Urutan Terendah (UR), maka kerjakan ke no.3, jika tidak, dengan kata lain data yang dicari dibawah Urutan Terendah (UR), maka kerjakan no.7
3. Tentukan nilai tengah denga rumus = (Urutan Terendah (UR) + Urutan Tertinggi (UT))/2
4. Jika data yang dicari < daripada Nilai Tengah maka Nilai Tengah mundur -1 ke arah UR 5. Jika data yang dicari > daripada Nilai Tengah maka Nilai Tengah maju + 1 ke arah UT
6. Jika data yang dicari = nilai tengah, maka pencarian langsung ketemu.
7. Jika data yang dicari > daripada Urutan Tertinggi (UT), maka Pencarian gagal
2. Ketika Urutam Tertinggi (UT) tidak lebih besar daripada Urutan Terendah (UR), maka kerjakan ke no.3, jika tidak, dengan kata lain data yang dicari dibawah Urutan Terendah (UR), maka kerjakan no.7
3. Tentukan nilai tengah denga rumus = (Urutan Terendah (UR) + Urutan Tertinggi (UT))/2
4. Jika data yang dicari < daripada Nilai Tengah maka Nilai Tengah mundur -1 ke arah UR 5. Jika data yang dicari > daripada Nilai Tengah maka Nilai Tengah maju + 1 ke arah UT
6. Jika data yang dicari = nilai tengah, maka pencarian langsung ketemu.
7. Jika data yang dicari > daripada Urutan Tertinggi (UT), maka Pencarian gagal
CONTOH STUDY
KASUS :
3 5 7 10 13 17
21 28
Diketahui x = 17
1. Mencari nilai low dan high, nilai
awal low dan high dapat ditentukan dari nilai terkecil dan nilai terbesar dari
suatu indeks.
Didalam contoh, nilai indeks terkecil=1 dan nilai indeks terbesar=8. Sehingga dapat ditentukan nilai low=1 dan nilai high=8.
Didalam contoh, nilai indeks terkecil=1 dan nilai indeks terbesar=8. Sehingga dapat ditentukan nilai low=1 dan nilai high=8.
2. Jika nilai low <= high maka
dapat mencari nilai mid. Jika nilai low>high, maka pencarian gagal. Dalam
soal diketahui low=1 dan high=8.Maka 1<=8, memenuhi syarat. Maka dapat
mencari nilai MID.MID = (low+high) div 2
= (1 + 8) div 2
= 9 div 2
= 4
3. Bandingkan nilai X dengan nilai
dari indeks yang dihasilkan dari nilai MID.X
MID17 > 10
4. Jika nilai X > MID maka
dapat dicari nilai low.LOW = MID + 1Jika nilai X < MID maka dapat
dicari nilai high.
HIGH = MID – 1
5. Jika nilai X = MID maka nilai MID
adalah nilai yang dicari. Dalam contoh menunjukkan jika nilai X > MID, maka
dapat dicari nilai low.Low = MID + 1= 4 + 1
= 5
6. Didapatkan sebuah nilai baru,
didalam contoh didapatkan nilai low baru. Sehingga persamaan baru yang didapat
:Low = 5 dan high = 8.
7. Nilai low dan high masih dapat
memenuhi syarat low<=high sehingga masih dapat mencari
nilai MID.MID = (low + high) div 2= (5 + 8) div 2
= 13 div 2
= 6
8. Bandingkan nilai X dengan nilai
indeks yang didapatkan dari perhitungan nilai
MID.X
MID17 = 17
Maka nilai x = nilai MID, maka nilai MID adalah nilai
yang dicari.
2. TEKNIK
PENCARIAN MAXMIN
A. Teknik Strait MAXMIN
Teknik Strait maksmin adalah teknik pencarian untuk mencari data atau nilai
yang lebih besar atau lebih kecil dari data yang lain dari kumpulan data
biasanya berbentuk array linier.
PENJELASAN
SEARCHING STRAIT MAXIMUM :
Untuk menjelaskan proses pencarian data terbesar atau data maksimum dari sekelompok data, di bawah ini akan diberikan contohnya terlebih dahulu.Jika diketahui sebuah sebuah larik data atau vector A yang memiliki 6 elemen data,sebagai berikut:
Untuk menjelaskan proses pencarian data terbesar atau data maksimum dari sekelompok data, di bawah ini akan diberikan contohnya terlebih dahulu.Jika diketahui sebuah sebuah larik data atau vector A yang memiliki 6 elemen data,sebagai berikut:
A : 50 20 43 15 66 55
Untuk menemukan data maksimum dari vector A, dapat dilakukan dengan cara sebagai berikut. Mula-mula elemen pertama dalam A, yaitu 50 di anggap sebagai data maksimum. Selanjutnya 50 kita bandingkan dengan elemen data yang kedua, yaitu 20. Karena 50 lebih besar dari 20, maka data maksimumnya tetap, yaitu 50. Selanjutnya, 50 kita bandingkan dengan elemen data yang ketiga yaitu 43. Harga data maksimum sebelumnya adalah lebih besar dari 43, sehingga data maksimumnya masih tetap, yaitu 50. Proses dilanjutkan untuk membandingkan kembali data maksimum sementara dengan data-data pada urutan selanjutnya secara berurutan hingga data pada urutan akhir. Ketika dibandingkan dengan data urutan yang ke-5, yaitu 66, ternyata 50 lebih kecil dari 66. Pada akhirnya setelah dibandingkan dengan keseluruhan data dalam vector A, data 66 merupakan data terbesar atau maksimum.
Untuk menemukan data maksimum dari vector A, dapat dilakukan dengan cara sebagai berikut. Mula-mula elemen pertama dalam A, yaitu 50 di anggap sebagai data maksimum. Selanjutnya 50 kita bandingkan dengan elemen data yang kedua, yaitu 20. Karena 50 lebih besar dari 20, maka data maksimumnya tetap, yaitu 50. Selanjutnya, 50 kita bandingkan dengan elemen data yang ketiga yaitu 43. Harga data maksimum sebelumnya adalah lebih besar dari 43, sehingga data maksimumnya masih tetap, yaitu 50. Proses dilanjutkan untuk membandingkan kembali data maksimum sementara dengan data-data pada urutan selanjutnya secara berurutan hingga data pada urutan akhir. Ketika dibandingkan dengan data urutan yang ke-5, yaitu 66, ternyata 50 lebih kecil dari 66. Pada akhirnya setelah dibandingkan dengan keseluruhan data dalam vector A, data 66 merupakan data terbesar atau maksimum.
2. PENJELASAN SEARCHING STRAIT MINIMUM
Pada kasus yang lain, jika diinginkan mencari data terkecil atau data minimum dari sekelompok data pada dasarnya langkah-langkah yang dilakukan adalah sama dengan algoritma prosedur pencarian data maksimum sebagaiman dijelaskan sebelumnya. Perbedaannya adalah terletak pada langkah ke-4, yaitu pertukaran data akan dilakukan jika data pada ukuran berikutnya memiliki harga yang lebih rendah dari nilai sebelumnya. Pada vector A dalam contoh sebelumnya, nilai 15 adalah merupakan data minimum atau terkecil dari semua data pada vector A.
Pada kasus yang lain, jika diinginkan mencari data terkecil atau data minimum dari sekelompok data pada dasarnya langkah-langkah yang dilakukan adalah sama dengan algoritma prosedur pencarian data maksimum sebagaiman dijelaskan sebelumnya. Perbedaannya adalah terletak pada langkah ke-4, yaitu pertukaran data akan dilakukan jika data pada ukuran berikutnya memiliki harga yang lebih rendah dari nilai sebelumnya. Pada vector A dalam contoh sebelumnya, nilai 15 adalah merupakan data minimum atau terkecil dari semua data pada vector A.
Waktu tempuh/time complexity yang digunakan untuk
menyelesaikan pencarian hingga mendapatkan solusi yang optimal terbagi atas :
– Best Case
– Average Case
– Worst Case
– Best Case
– Average Case
– Worst Case
BEST CASE
Keadaan yang tercapai jika elemen pada himpunan A disusun secara increasing (menaik). Dengan perbandingan waktu n-1 kali satuan operasi.
Keadaan yang tercapai jika elemen pada himpunan A disusun secara increasing (menaik). Dengan perbandingan waktu n-1 kali satuan operasi.
CONTOH KASUS
BEST CASE :
Pada Himpunan A yang berisi {5,-4,9,7} dilakukan pencarian elemen max & min dengan menggunakan proses STRAIT MAXMIN. Berapa elemen maxmin yang didapat dan jumlah operasi perbandingan yang dilakukan.
Pada Himpunan A yang berisi {5,-4,9,7} dilakukan pencarian elemen max & min dengan menggunakan proses STRAIT MAXMIN. Berapa elemen maxmin yang didapat dan jumlah operasi perbandingan yang dilakukan.
Penyelesaian :
Elemen Max = 9, dan elemen min = -4
Jumlah operasi perbandingan adalah (3 *4/2-1)=5 kali satuan operasi
Elemen Max = 9, dan elemen min = -4
Jumlah operasi perbandingan adalah (3 *4/2-1)=5 kali satuan operasi
Tentukan atau cari bilangan Max & Min serta jumlah
operai perbandingan yang dilakukan.
Penyelesian :
Untuk masalah tersebut dapat digunakan procedure STRAITMAXMIN yang menghasilkan bilangan min = 3 bilangan max = 15, operasi perbandingan mencari bilangan MaxMin dari himpunan tersebut adalah (n-1) = 4 kali operasi.
Untuk masalah tersebut dapat digunakan procedure STRAITMAXMIN yang menghasilkan bilangan min = 3 bilangan max = 15, operasi perbandingan mencari bilangan MaxMin dari himpunan tersebut adalah (n-1) = 4 kali operasi.
AVERAGE CASE
Jika pencarian elemen MaxMin dilakukan pada elemen dalam himpunan yang tersusun secara acak ( tidak decreasing / tidak increasing ) jumlah operasi. Perbandingan yang dilakukan adalah rata – rata waktu tempuh best case dan worst case yaitu ½[(n-1) + 2(n-1)]=(3n/2 – 1)kali
Jika pencarian elemen MaxMin dilakukan pada elemen dalam himpunan yang tersusun secara acak ( tidak decreasing / tidak increasing ) jumlah operasi. Perbandingan yang dilakukan adalah rata – rata waktu tempuh best case dan worst case yaitu ½[(n-1) + 2(n-1)]=(3n/2 – 1)kali
CONTOH KASUS
AVERAGE CASE :
Pada Himpunan A(1) = 15, A(2) = 7, A(3) = 11, A(4) = 3, A(5) = 5,A(6) = -2 dilakukan pencarian elemen max & min dengan menggunakan proses STRAIT MAXMIN. Berapa elemen maxmin yang didapat dan jumlah operasi perbandingan yang dilakukan.
Pada Himpunan A(1) = 15, A(2) = 7, A(3) = 11, A(4) = 3, A(5) = 5,A(6) = -2 dilakukan pencarian elemen max & min dengan menggunakan proses STRAIT MAXMIN. Berapa elemen maxmin yang didapat dan jumlah operasi perbandingan yang dilakukan.
Penyelesaian :
Elemen Max = 15, dan elemen min = -2 Jumlah operasi perbandingan adalah (3 (6/2)-1)=8 kali satuan operasi.
Elemen Max = 15, dan elemen min = -2 Jumlah operasi perbandingan adalah (3 (6/2)-1)=8 kali satuan operasi.
WORST CASE
Terjadi jika elemen dalam himpunan disusun secara decreasing ( menurun ). Dengan Operasi perbandingan sebanyak 2 ( n-1) kali satuan operasi.
Terjadi jika elemen dalam himpunan disusun secara decreasing ( menurun ). Dengan Operasi perbandingan sebanyak 2 ( n-1) kali satuan operasi.
CONTOH KASUS
WORST CASE :
Cari elemen MaxMin dan jumlah Operasi perbandingan yang dilakukan terhadap himpunan A yang disusun decreasing. A(1) = 15, A(2) = 11, A(3) = 7, A(4) = 5, A(5) = 3.
Cari elemen MaxMin dan jumlah Operasi perbandingan yang dilakukan terhadap himpunan A yang disusun decreasing. A(1) = 15, A(2) = 11, A(3) = 7, A(4) = 5, A(5) = 3.
Penyelesaian :
untuk masalah tersebut dapat digunakan procedure STRAITMAXMIN adalah elemen max = 15 dan elemen min = 3, operasi perbandingan untuk elemen MaxMin tersebut adalah 2(5-1) = 8 kali satuan operasi.
untuk masalah tersebut dapat digunakan procedure STRAITMAXMIN adalah elemen max = 15 dan elemen min = 3, operasi perbandingan untuk elemen MaxMin tersebut adalah 2(5-1) = 8 kali satuan operasi.
B. TEKNIK
DENGAN TEKNIK D AND C
Dengan Prinsip Dasar Metode Devide dan akan dapat
dipecahkan suatu permasalahan proses Searching elemen Max and Min dengan teknik
D and C.
Contoh :
Tentukan elemen MAXMIN suatu array A yang terdiri 9 bil :
Tentukan elemen MAXMIN suatu array A yang terdiri 9 bil :
A(1) = 22
A(2) = 13
A(3) = -5
A(4) = -8
A(5) = 15
A(6) = 60
A(7) = 17
A(8) = 31
A(9) = 47
A(2) = 13
A(3) = -5
A(4) = -8
A(5) = 15
A(6) = 60
A(7) = 17
A(8) = 31
A(9) = 47
Lalu Proses tree call dr setiap elemen yg ditunjuk
pada bagan tree tersebut diatas. Dengan cara, membalik terlebih dahulu posisi
tree dr bawah ke atas. Lalu mengisinya dengan elemen-elemnnya sesuai dengan
bagan tree. Perhatikan bagan tree call ini :
Berikut Contoh soal dan jawaban
materi Teknik Searching
1.
Terdapat deret angka sebagai berikut:
80,45,21,100,23,67,43,20,67,43,20,90,99,46,75,73,29
Buat
algoritma untuk mencari angka 43 teknik linier search
Jawaban:
I = 1 , X
=43
Nilai I <
Nilai X , 80<43 I = 1+1=2
Nilai I <
Nilai X, 45<43 I = 2+1=3
Nilai I <
Nilai X , 21<43 I = 3+1=4
Nilai I <
Nilai X , 100<43 I= 4+1=5
Nilai I <
Nilai X , 23<43 I = 5+1=6
Nilai I <
Nilai X , 67<43 I = 6+1=7
Nilai I <
Nilai X , 43<43 I = 7+1=8
Nilai I =
Nilai X, 43=43, maka pencarian selesai
Jadi, I =8,
X=43.
2.
Terdapat deret angka sebagai berikut:
12,16,20,25,29,34,45,56,60,67,70,78,89,93,99
Buat
algoritma untuk mencari angka 45 dengan teknik Binery Search
Jawaban
L=1 , H=15,
X=45
L<=H,1
<=15, maka
Mid= (L+H)
Div 2 = (1+15) Div 2
Mid=8
X < mid
45<56,
maka H=mid-1 =8-1
H=7
L<= H
1<=7
Maka mid =
(L+H) Div 2 = (1+7) div 2
Mid = 4
X>mid
45>25,maka
L=mid+1=4+1
L=5
L<=H ,
5<=7
Maka, mid =
(L+H)div2 = (5+7)div2
Mid = 6
x>mid
45>34,maka
L=mid+1 = 6+1
L=7
L<=H ,
7<=7
Maka,mid =
(L=H)div2 = (7+7)div2
Mid=7
X=mid
45=45 maka
pencarian selesai
Jadi untuk
x=45,maka L=7 H=7
3.
Terdapat Himp.A Yang Berisi 5 Buah Bilangan telah disusun secara
Increasing dengan
A[0]=5, A[1]=10,
A[2]=15, A[3]=20, A[4]=25.
Tentukan/cari
bilangan Max&Min serta jumlah operasi perbandingan yang dilakukan (keadaan
Best case).
Jawaban:
Max=min=5
For i = 2 to
5
If
A[2]>max
10>5 ? ya
,maka max=10
If
A[3]>max
15>10 ?
ya, maka max=15
If
A[4]>max
20>15 ?
ya, maka max=20
If
A[5]>max
25>20
? ya, maka max=25(Pencarian selesai)
Jadi max=25
dan min =5 ,dengan operasi perbandingan sebanyak 4
kali.
4.
Terdapat Himp.A yang berisi 5 buah bilangan telah di susun secara
decreasing dengan
A[0]=30,
A[1]=25, A[2]=20, A[3]=15, A[4]=-10.
Tentukan/cari
bilangan Max&Min serta jumlah operasi perbandingan yang dilakukan (keadaan
worst case)
Jawaban:
30,25,20,15,-10
Max=min=30
For i = 2 to
5
If
A[2]>max
25>30 ?
tidak ,maka max=30
If
A[2]<min
25<30 ?
ya ,maka min=25
If
A[3]>max
20>30 ?
tidak, maka max=30
If
A[3]<min
20<25 ?
ya, maka min=20
If
A[4]>max
15>30 ?
tidak, maka max=30
If
A[4]<min
15<20 ?
ya, maka min=15
If
A[5]>max
-10>30 ?
tidak, maka max=30
If
A[5]<min
-10<15
? ya, maka min=-10 (Pencarian selesai)
Jadi Max=30
min=-10 , dengan jumlah perbandingan sebanyak 8 kali
5.
Terdapat Himp.A yang berisi 5 buah bilangan telah di susun secara
decreasing dengan
A[0]=25,
A[1]=20, A[2]=35, A[3]=30, A[4]=10.
Tentukan/cari
bilangan Max&Min serta jumlah operasi perbandingan yang dilakukan (keadaan
averaget case).
Jawaban :
Max=min=25
For i = 2 to
5
If
A[2]<min 20<25 ? ya ,maka min=20
If
A[3]>max 35>25 ? ya, maka max=35
If
A[3]<min 35<20 ? tidak, maka min=20
If
A[4]>max 30>35 ? tidak, maka max=35
If
A[4]<min 30<20 ? tidak, maka min=20
If
A[5]>max 10>35 ? tidak, maka max=35
If
A[5]<min 10<20 ? ya,maka min=10 (Pencarian selesai)
Jadi max=35
min=10 dengan operasi perbandingan sebanyak 7 kali
6.
Tentukan elemen Max&Min suatu array A yang terdiri 11 bil :
A[1]=33,
A[4]=88, A[7]=27, A[10]=-2
A[2]=-7, A[5]=25, A[8]=-9, A[11]=10
A[3]=23,
A[6]=80, A[9]=44,
Gunakan
Searching dengan Tehnik D And C!
Jawaban :
Jadi max dan
min teknik D dan C yaitu : Max = 88 , Min = -2
Tidak ada komentar:
Posting Komentar