Pencarian(searhing) merupakan proses yang sangat penting dalam pengolahan data. Proses pencarian adalah menemukan nilai(data) tertentu didalam sekumpulan data yang bertipe sama. Sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi.
Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah Kata kunci dan dengan langkah-langkah tertentu akan mencari rekaman dengan kata kunci tersebut. Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan atau tidak ditemukan.
Macam-macam Algoritma (Searching)
1. Pencarian sekuensial (Sequential searching)
Pencarian Sekuensial (sequential searching) atau pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana. Pencarian beruntun adalah proses yang membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa.
Perharikan larik L dibawah ini dengan n = 6 elemen :
13
|
16
|
14
|
21
|
76
|
15
|
1
|
2
|
3
|
4
|
5
|
6
|
Misal nilai yang di cari adalah : x = 21
Maka elemen yang dibandingkan (berturut-turut) : 13, 16, 14, 21 (ditemukan!)
Indeks larik yang di kembalikan : idx = 4
Setiap Elemen larik L dibandingkan dengan x mulai dari elemen pertama L[1]. Aksi perbandingan dilakukan selama indeks i belum melebihi n dan L[i] tidak sama dengan x. Aksi pembanding dihentikan bila L[i] = x atau i = N. Elemen terakhir, L[n], diperiksa secara khusus. Keluaran yang dihasilkan oleh prosedure pencarian adalah peubah idx yang berisi indeks larik tempat x ditemukan. Jika x tidak ditemukan, idx diisi dengan nilai -1.
Procedure pencarian beruntun :
Prosedure SeqSearch (input L : larik, input n : integer, input x : integer, output idx : integer )
I.S. : {X dan elemen-elemen larik L[1..n] }
F.S. : {idx berisi indeks larik L yang berisi nilai x tidak ditemukan, maka idx diisi dengan nilai -1}
Kamus
i : integer {pencacah indeks larik}
Algoritma :
i <- 1
while (i < n ) and (L[i] =/ x ) do
i <- i + 1
endwhile
{ i = n or L[i] = x }
if L[i] = x then { x ditemukan }
idx <- i
else
idk <- -1
endif
2. Pencarian Biner (binary search)
Terdapat metode pencarian pada data terurut yang paling efficient, yaitu metode pencarian bagi dua atau pencarian biner (binary search). Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mendasari metode ini. Data yang disimpan di dalam larik harus sudah terurut. data terurut yang paling efficient, yaitu metode pencarian bagidua atau pencarian biner (binary search).
Cara kerja Binary Search
Misal indeks kiri adalah i dan indeks kanan adalah j. Pada mulanya kita, inisialisasi i dengan 1 dan j dengan n.
Langkah 1 : Bagi dua larik pada elemen tengah. Elemen tengah adalah elemen
dengan indeks k = (i + j) div 2.
(Elemen tengah L[k], membagilarik menjadi dua bagian, yaitu bagian kiri L[i..j] dan bagian kanan L[k+1..j] )
Langkah 2 : Periksa apakah L[k] = x. Jika L[k] = x, pencarian selesai sebab x sudah ditemukan. Tetapi jika L[k] =/ x, harus ditentukan apakah pencarian akan dilakukan di larik bagian kiri atau bagian kanan. Jika L[k] < x, maka pencarian dilakukan lagi pada larik bagian kiri. Sebaliknya, jika L[k] > x, pencarian dilakukan lagi padalarik kanan.
Langkah 3 : Ulang langkah 1 hingga x ditemukan atau i > j (yaitu, ukaran larik sudah nol!)
Ilustrasi pencarian bagidua (Binary Search) : Misalkan diberikan larik L dengan delapan buah elemen yang sudah terurut menurun seperti dibawah ini :
81
|
76
|
21
|
18
|
16
|
13
|
10
|
7
|
i=1
|
2
|
3
|
4
|
5
|
6
|
7
|
8=j
|
(i) Elemen yang ditarik adalah x = 18.
Langka 1 :
Ii = 1 dan j = 8
Indeks elemen k = (1+8) div 2 = 4 (elemen yang diarsir)
81
|
76
|
21
|
18
|
16
|
13
|
10
|
7
| |
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
| |
Kiri
|
Kanan
| |||||||
Langkah 2 :
Perbandingkan L[4] = 18 ? Ya! (x ditemukan, proses pencarian selesai)
(ii) Misalkan elemen yang dari adalah x = 16.
Langka 1 :
Ii = 1 dan j = 8
Indeks elemen k = (1+8) div 2 = 4 (elemen yang diarsir)
81
|
76
|
21
|
18
|
16
|
13
|
10
|
7
| |
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
| |
Kiri
|
Kanan
| |||||||
Langkah 2 :
Perbandingkan L[4] = 16 ? Tidak! Harus diputuskan apakah pencarian akan dilakukan dibagian kiri atau dibagian kanan dengan pemeriksaan sebagai berikut :
Pembandingkan : L[4] > 16 ? Ya!, maka pencarian pada larik bagian kanan dengan i = k + 1 = 5 dan j = 8 (tetap)
16
|
13
|
10
|
7
| ||
i=5
|
6
|
7
|
8=j
| ||
Langka 1’ :
Ii = 5 dan j = 8
Indeks elemen k = (5+8) div 2 = 6 (elemen yang diarsir)
16
|
13
|
10
|
7
| ||
i=5
|
6
|
7
|
8=j
| ||
Kiri
|
Kanan
| ||||
Langkah 2’ :
Perbandingkan L[6] = 16 ? Tidak! Harus diputuskan apakah pencarian akan dilakukan dibagian kiri atau dibagian kanan dengan pemeriksaan sebagai berikut :
Pembandingkan : L[6] > 16 ? Tidak!, maka pencarian pada larik bagian kanan dengan i = 5 (tetap) dan j = k – 1 = 5
16
| ||
5
|
Langka 1’’ :
Ii = 5 dan j = 8
Indeks elemen k = (5+8) div 2 = 6 (elemen yang diarsir)
16
| ||
5
|
Langkah 2’’ :
L[5] = 16 ? Ya! (x ditemukan, proses pencarian selesai)
Procedure pencarian Binary Search
procedure BinarySearch (input L : larikint, input n : integer, input x : integer,
output idx : integer )
Kamus :
i, j : integer { indeks kiri dan indeks kanan larik }
k : integer { indeks elemen tengah }
ketemu : Boolean { flag untuk memutuskan apa x ditemukan }
Algoritma :
i <- 1 { ujung kiri larik }
j <- n { ujung kanan larik }
ketemu <- false { asumsikan x belum ditemukan }
while (not ketemu ) and ( i < j ) do
k <- (i + j) div 2 { bagi larik pada posisi k }
if (L[k] = x) then
ketemu <- true
else
if (L[k] > x) then
{ Lakukan pencarian pada bagian kanan, set indeks ujung kiri larik yang baru }
i <- k + 1
else
{ Lakukan pencarian pada larik bagian kiri, set indeks ujung kanan larik yang baru }
j <- k – 1
endif
endif
endwhile
{ ketemu = true or i > j }
if ketemu then { x ditemukan }
idx <- k
else { x tudak ditemukan didalam larik }
idx <- -1
endif
Sumber : 1. Munir, Renaldi. (2011). Algoritma & Pemrogramman Dalam Bahasa Pascal dan C. (edisi revisi). Bandung ; INFORMATIKA.
2. http://andiagusta.blogspot.co.id/2014/02/algoritma-pencarian-searching.html
0 komentar:
Posting Komentar