Dalam Teknik Searching yang termasuk Tehnik pencarian Tunggal adalah

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.
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:

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.

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.

Waktu tempuh/time complexity yang digunakan untuk menyelesaikan pencarian hingga mendapatkan solusi yang optimal terbagi atas : – 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.

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.

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 :
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

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.

Penyelesaian :
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.

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.

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.

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 :

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

Dalam Teknik Searching yang termasuk Tehnik pencarian Tunggal adalah

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 :

Dalam Teknik Searching yang termasuk Tehnik pencarian Tunggal adalah

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 :

Dalam Teknik Searching yang termasuk Tehnik pencarian Tunggal adalah
Dalam Teknik Searching yang termasuk Tehnik pencarian Tunggal adalah

Jadi max dan min teknik D dan C yaitu : Max = 88 , Min = -2