Analysis Homework - Spring Semester 2002.docx Murdoch Bridging Study Guide - CWL.pdf Fin-302-Final-Report.docx SCarpenterM6L8Assignment3.java Management 215 Chapter 2 Summary.docx alexander_godoy_tarea_2.docx
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 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. 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 :
A : 50 20 43 15 66 55
2. PENJELASAN SEARCHING STRAIT MINIMUM
Waktu tempuh/time complexity yang digunakan untuk menyelesaikan pencarian hingga mendapatkan solusi yang optimal terbagi atas : – Best Case – Average Case – Worst Case
BEST CASE
CONTOH KASUS
BEST CASE :
Penyelesaian : 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 :
AVERAGE CASE
CONTOH KASUS
AVERAGE CASE :
Penyelesaian :
WORST CASE
CONTOH KASUS
WORST CASE :
Penyelesaian : 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 :
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 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 |