ALGORITMA BEBERAPA TEKNIK SEARCHING DALAM PEMROGRAMAN KOMPUTER

-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

16
5
Low/high

ITERASI 3
Langkah 1:
Low = 5  dan High=5
Elemen tengah  Middle = (5+5) div 2 = 10 div 2 = 5
16
5
middle

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.

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