1. Tehnik Sequential Search / Linier Search
Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Misalnya pada soal dibawah. Disitu kita mencari angka 43. angka 43 berada pada posisi ke -7. Dibandingkan 1 per 1 sampai data tersebut ditemukan/bandingkan dari posisi ke-1 sampai ke posisi ke-7.
Berikut contoh penyelesaian soal Linier Searh
Terdapat deret angka sebagai berikut :
80 , 45 , 21 , 100 , 23 , 67 , 43 , 20 , 90 , 99 , 46 , 75 , 73 , 29 .
Buat algoritma untuk mencari angka 43 teknik Linear Search
Jawab:
80, 45, 21, 100, 23, 67, 43, 20, 90, 99, 46, 75, 73, 29
X = 43
I = 1
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
Jadi, I= 7 dan X =43
Algoritmanya :
1. Tentukan I = 1
2. Ketika Nilai ( I ) < > X Maka Tambahkan
I = I + 1
3. Ulangi Langkah No.2 Sampai Nilai ( I ) = X
4. Jika Nilai ( I ) = N + 1 Maka Cetak “
Pencarian Gagal “ Selai Itu Cetak “ Pencarian Sukses “ .
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
2. Pencarian
Binary Search
1. Metode pencarian yang
diterapkan pada sekumpulan data yang sudah terurut (menaik maupun menurun)
2. Metode ini digunakan
untuk melakukan pencarian secara cepat dengan data yang sudah terurut.
Contoh soal:
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 binary search.
Jawab :
12,16,20,25,29,34,45,56,60,67,70,78,89,93,99
X = 45
L = 1
H = 15
L<=H, 1<=15
Mid = (L+H) Div 2
= (1+15) Div 2
= 8
X<Mid, 45<56
H = Mid -1
= 8-1
= 7
L<=H, 1<=7
Mid = (L+H) Div 2
= (1+7) Div 2
= 4
X>Mid, 45>25
L = Mid + 1
= 4 +1
= 5
Jadi L = 5 dan H = 7
L<=H,
5<=7
Mid = (L+H) div 2
= (5+7) div 2
= 6
X>Mid, 45>35
Pencarian
Gagal
Penjelasan :
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.
4.
Jika sama maka catat
posisi dan cetak kemudian berhenti.
5.
Jika lebih besar maka
akan dilakukan pencarian kembali kebagian kanan dengan posisi awal posisi
tengah +1 dan posisi akhir tetap kemudian ulangi mulai poin 2.
Jika lebih kecil maka akan
di lakukan pencarian kembali ke bagian kiri dengan nilai posisi awal tetap dan
nilai posisi akhir = posisi tengah-1 kemudian ulangi mulai poin 2.
1. Best Case Adalah jika data yang dicari terletak di indeks
array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk
pencarian data sangat sebentar (minimal)....
Contoh soal :
Terdapat Himpunan .A yang berisi 5 buah bilangan telah
disusun secara increasing dengan A[0]=5, A[1]=10, A[2]=15, A[3]=20, A[2]=25.
Tentukan/Cari Bilangan Max & Min serta jumlah operasi perbandingan yang
dilakukan (Keadaan Best Case)
Jawab :
A[0]=5,
A[1]=10, A[2]=15, A[3]=20, A[4]=25
Max =Min=5
1. If A[1]>
max
A[1]>5
10>5 ? ya max = 10
2. If A[2]>
max
A[2]>10
15>10? ya, max = 15
3. If A[3]>
max
A[3]>15
20>15? ya, max = 20
4. If A[4]>
max
A[4]>20
25>20 ? ya, max = 25
Jadi,
Max= 25 Min=5, dan Jumlah operasi perbandingannya sebanyak n-1 ( 5-1 ) = 4 kali
Penjelasan :
Keadaan yang tercapai jika elemen pada himpunan
A disusun secara
increasing (menaik). Dengan perbandingan waktu n-1 satuan
operasi.
4.Tekhnik Worst Caes
Tekhnik Worst Caes adalah jika data yang dicari terletak di indeks
array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).
Contoh Soal :
Terdapat himpunan A yang berisi 5 buah bilangan telah disusun
secara increasing dengan A[0]=30, A[1]=25, A[2]=20 A[3]=15, A[2]=10.
Tentukan/Cari Bilangan Max & Min serta jumlah operasi perbandingan
yang
dilakukan (keadaan worst case).
Jawab :
A[0]=30,
A[1]=25, A[2]=20, A[3]=15, A[4]=10
Max =Min=30
For i = 2 to 5
1.
If A[1]> max
A[1]>30
25>30 ? tidak max = 30
2.
Else If A[1]< min A[1]<30
25<5 ? ya, min = 25
3.
If A[2]> max A[2]>30
20>30 ? tidak, max = 30
4.
Else If A[2]< min
A[2]<30
20<30 ? ya, min = 20
5.
If A[3]> max A[3]>30
15>30? tidak,
max = 30
6.
Else If A[3]< min A[3]<30
15<30 ? ya, min = 15
7.
If A[4] > max A[4] >
30
10 > 30 ? Tidak, max =30
8.
else if A[4] < min A[4]
< 30
10 < 30 ? Ya, min =10
Jadi, Max= 30 Min=10, dan
Jumlah operasi perbandingannya
sebanyak 2 (n-1)= 2 ( 5-1
) = 8 kali
5. Tekhnik Averaget 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 soal :
Terdapat himpunan A yang berisi 5 buah bilangan telah disusun
secara increasing 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 average case)
Jawab :
Max =Min=25
For i = 2 to 5
1.
If A[1]> max
A[1]>25
20>25 ? tidak max = 25
2.
Else If A[1]< min A[1]<25
20<25 ? ya, min = 20
3.
If A[2]> max A[2]>25
35>25 ? ya, max = 35
4.
If A[3]> max
A[3]>35
30>35 ? tidak, max = 35
5.
Else If A[3]< min A[3]<35
30<35 ? ya, min = 30
6.
If A[4]> max A[4]>35
10>35 ? tidak, max = 35
7.
Else If A[4]< min A[4]<35
10<35 ? ya, min = 35
Elemen Max = 35 dan Elemen Min =10
½ [ (n-1) + 2 (n-1) ] = ( 3n/2 -1
)
= ( 3.5/2 -1 )
= ( 15/2-1)
= (15/2 – ½)
= (14/2)
=7
Jadi operasi perbandingan sebanyak
7 kali
6. Tekhnik Searching D dan C
Tentukan Elemen MaxMin suatu array A yang terdiri
11 bilangan:
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
Tidak ada komentar:
Posting Komentar