-LUNTAS ILMU- 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
- proses update atau penghapusan data à sebelumnya melakukan proses pencarian data.
- 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 :
· Tehnik Sequential Search / Linier Search
· Tehnik Binary Search
PENCARIAN SEQUENTIAL
· Merupakan algoritma pencarian yang sangat sederhana.
· Proses pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan dan seluruh elemn sudah diperiksa.
13 16 14 21 76 21
Nilai yang dicari: 21
Maka elemen yang diperiksa : 13 16 14 21
Index ketemu : 4
Nilai yang dicari: 13
Maka elemen yang diperiksa : 13
Index ketemu : 1
Nilai yang dicari: 15
Maka elemen yang diperiksa : 13 16 14 21 76 21
Index ketemu : 0
Algoritma dari proses Pencarian diatas adalah:
1. Tentukan i=1, Ketemu = 0.
2. Masukan Nilai X à nilai yang dicari.
3. Jika Nilai[i] <> X maka i=i+1, kembali kelangkah 2.
4. Jika Nilai[i] = X maka Ketemu =i.
5. Jika Ketemu = 0 maka Cetak “nilai X tidak ketemu”
6. Jika tidak (Ketemu <>0)Cetak “nilai X ketemu pada posisi Ketemu”
7. Selesai
Pencarian Binary Search
· Metode pencarian yang diterapkan pada sekumpulan data yang sudah terurut (menaik maupun menurun)
· Metode ini digunakan untuk melakukan pencarian secara cepat dengan data yang sudah terurut.
Konsep Pencarian Binary/Bagi Dua
· Pilih Indek Kiri (Low) dan Indek Kanan (High)
· Langkah 1:
Bagi dua elemen larik pada elemen tengah.
Elemen tengah adalah elemen dengan indek middle=(low+high) div 2.
Elemen tengah (middle), akan membagi array menjadi 2 bagian yaitu:
ð Bagian kiri, dengan index LARIK[Low .. middle-1]
ð Bagian Kanan, dengan index LARIK[middle+1..High]
· Langkah 2:
ð Periksa apakah LARIK[middle] = X , pencarian akan dihentikan sebab X sudah ditemukan
ð Jika LARIK[middle] <> X, maka kita tentukan pencarian akan dilakukan disebelah kiri atau kanan.
§ Jika LARIK[middle] < X, maka pencarian dilakukan dibagian kiri LARIK
§ Jika LARIK[middle] > X, maka pencarian dilakukan di bagian kanan LARIK
· Langkah 3:
Ulangi langkah 1 sampai dengan X ditemukan, atau low > high (menentukan ukuran larik sudah 0).
Ilustrasi Pencarian Bagi Dua.
81
|
76
|
21
|
18
|
16
|
13
|
10
|
7
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
Low
|
|
|
|
|
|
|
High
|
1. Misalkan elemen yang dicari adalah X=18.
Langkah 1:
Low = 1 dan High = 8
Elemen tengah Middle = (1+8) div 2 = 9 div 2 = 4
81
|
76
|
21
|
18
|
16
|
13
|
10
|
7
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
Low
|
|
|
Middle
|
|
|
|
High
|
Langkah 2:
Larik[4] = X ? (18 = 18) true à X ditemukan, pencarian dihentikan.
2. Misalkan elemen yang dicari adalah X=16.
ITERASI 1
Langkah 1:
Low = 1 dan High = 8
Elemen tengah Middle = (1+8) div 2 = 9 div 2 = 4
81
|
76
|
21
|
18
|
16
|
13
|
10
|
7
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
Low
|
|
|
Middle
|
|
|
|
High
|
kiri
|
|
kanan
|
Langkah 2:
Larik[4] = X ? (18 = 16) FALSE, sehingga diputuskan pencarian di kiri atau dikanan.
Jika Larik[4] > 16 ?, (18 > 16) TRUE, lakukan pencarian disebelah kanan dengan Low = middle+1 à 4+1 = 5 dan High = 8, Tetap.
16
|
13
|
10
|
7
|
5
|
6
|
7
|
8
|
low
|
|
|
High
|
ITERASI 2
Langkah 1:
Low = 5 dan High=8
Elemen tengah Middle = (5+8) div 2 = 13 div 2 = 6
16
|
13
|
10
|
7
|
5
|
6
|
7
|
8
|
low
|
middle
|
|
High
|
Langkah 2:
Larik[6] = X ? (13 = 16) FALSE, sehingga diputuskan pencarian di kiri atau dikanan.
Jika Larik[6] > 16 ?, (13 > 16) FALSE, lakukan pencarian disebelah KIRI dengan Low = 5 (TETAP) dan High = middle-1 = 5
ITERASI 3
Langkah 1:
Low = 5 dan High=5
Elemen tengah Middle = (5+5) div 2 = 10 div 2 = 5
Langkah 2:
Larik[5] = X ? (16 = 16) TRUE (X ditemukan , pencarian dihentikan)
3. Misalkan elemen yang dicari X=100.
Gambarkan langkah-langkah penyelesaiannya?
Dari ilustrasi diatas dapat dibuat algoritma sebagai berikut:
(dengan data urut menurun/ descending)
1. Masukan Bil yang dicari X
2. tentukan low=1 dan high = N
3. Tentukan nilai tengah : middle = (low + high) div 2
4. Cek, jika LARIK[middle] = X maka Nilai X yang dicari ditemukan, kelangkah 8
5. jika LARIK[middle] > X maka low=middle+1, kelangkah 7
6. jika LARIK[middle] < X maka high=middle-1, kelangkah 7
7. Jika low > high, “bil X tidak ditemukan” dan kelangkah 8, jika tidak kelangkah 3.
8. selesai.
Tugas :
1. buatlah algoritma binary search untuk data yang urut menaik / ascending. Dari algoritma diatas
2. buatlah flowchartnya.
ALGORITMA bentuk lain (ada pada slide) à untuk data urut menaik/ascending
1. Low = 1 , High = N
2. Ketika Low <= High Maka kerjakan langkah No .3,
Jika tidak Maka kerjakan langkah No.7
3. Tentukan index tengah dengan rumus
Middle= ( Low + High ) Div 2
4. Jika X < LARIK[middle] /Nil. Tengah Maka High = Mid –1
5. Jika X > LARIK[middle] /Nil. Tengah Maka Low = Mid +1
6. Jika X = LARIK[middle] /Nil. Tengah Maka Nil. Tengah = Nil. Yg dicari
7. Jika X > High Maka Pencarian GAGAL
2. Tehnik Pencarian Nilai MAXMIN :
ð Tehnik StaritMAXMIN
ð Tehnik D and C
Teknik yangt digunakan untuk mencari nilai maksimum dan minimum dari sekumpulan nilai.
- Tehnik Pencarian MAXMIN
Searching dengan Tehnik STRAITMAXMIN
Waktu tempuh yang digunakan untuk menyelesaikan pencarian hinggan mendapatkan solusi yang optimal terbagi atas :
a. Best Case
b. Average Case
c. worst Case
Algoritma dari Proses Pencarian adalah (ada pada slide):
1. Masukan N, tentukan i=1.
2. Tentukan max dan min = A[i]
3. i = 2
4. Jika i<= N maka kelangkah 5, jika tidak kelangkah 8
5. jika A[i] > max maka max=A[i] dan kelangkah 7
6. jika tidak maka (jika A[i] < min maka min = A[i].
7. i = i+1, ulangi langkah 4.
8. cetak max dan min
program straitmaxmin;
var
i,N:integer;
max,min : integer;
A : array[1..10] of integer;
begin
write('masukan N = '); readln(N);
for i:=1 to N do
readln(A[i]);
max := A[1]; min := A[1];
for i:=2 to N do
if A[i] > max then max:=A[i]
else if A[i] < min then min := A[i];
writeln;
writeln('nilai max min= ',max:3, min:3);
end.
|
masukan N = 5
2
5
1
6
4
nilai max min = 6 1
-----------------
masukan N = 6
7
5
3
9
6
2
nilai max min = 9 2
|
Searching dengan teknik D and C. untuk kode program search anda bisa meluncur ke sini
