Bab9 (Pencarian)

   Pencarian merupakan sebuah algoritma dasar yang sering diperlukan dalam
pembuatan program. Berbagai algoritma pencarian telah diciptakan dan dapat
digunakan. Pemahaman tentang beberapa algoritma pencarian dasar perlu
diketahui, termasuk cara penggunaannya dalam program.

     1. Memahami konsep pencarian
     2. Mengenal beberapa algoritma pencarian
     3. Menerapkan algoritma pencarian dalam program

   Konsep Pencarian
Pencarian adalah proses menemukan nilai (data) tertentu dari dalam
sekumpulan nilai yang bertipe sama (tipe dasar maupun tipe bentukan).
Dengan kata lain, algoritma pencarian adalah algoritma yang mengambil input
berupa persoalan dan mengembalikan penyelesaian berupa penemuan nilai yang
dicari dalam persoalan inputan.
   Proses pencarian seringkali diperlukan pada saat program perlu
mengubah atau menghapus nilai tertentu (sebelum bisa mengubah atau
menghapus, perlu mencari dulu apakah nilai tersebut ada dalam kumpulan
nilai tersebut). Kasus lain yang memerlukan algoritma pencarian adalah
penyisipan data ke dalam kumpulan data (perlu dimulai dengan pencarian
apakah data tersebut telah ada sehingga terhindar dari duplikasi data).

   Pencarian Sekuensial
Pencarian sekuensial (sequential search) adalah proses membandingkan
setiap elemen larik (array) satu persatu dengan nilai yang dicari secara
beruntun, mulai dari elemen pertama sampai elemen yang dicari sudah
ditemukan, atau sampai seluruh elemen sudah diperiksa.
   Algoritma pencarian sekuensial ini cocok untuk pencarian nilai tertentu
pada sekumpulan data terurut maupun tidak. Keunggulan algoritma ini adalah
dalam mencari sebuah nilai dari sekumpulan kecil data. Algoritma ini
termasuk algoritma yang sederhana dan cepat karena tidak memerlukan
proses persiapan data (misalnya: pengurutan).

PROCEDURE SeqSearch(input L:array[1..N] of integer, input N:integer,input X:integer, output idx : integer)

IS : Terdapat array berisi data angka FS : Memberikan hasil data ketemu atau tidak ketemu

KAMUS DATA k : integer

BEGIN k ⬅ 0 WHILE ((k<N) AND (L[k] !=X)) k ⬅ k+1 ENDWHILE IF ((L[k]=X)&&(k<N)) idx ⬅ k+1 ELSE   idx                 ⬅             -1  ENDIF END

Prosedur di atas memerlukan parameter input berupa:

   ⇨ L yaitu sebuah larik (array) tempat menyimpan data yang diinginkan,

   ⇨ N yaitu jumlah elemen larik (atau index terbesar),

   ⇨ X yaitu nilai data yang ingin dicari

serta sebuah parameter output berupa variabel idx bertipe integer yang akan

mengembalikan posisi ditemukannya data yang dicari apabila ketemu dan akan

mengembalikan nilai -1 jika data tidak ditemukan.

Prosedur dimulai dengan inisialisasi pencacah iterasi (k ⬅ 0). Kemudian

pencarian dilakukan dengan perulangan yang membandingkan setiap elemen

larik secara berurutan dari elemen pertama hingga terakhir dengan nilai data

yang diinginkan. Perulangan berakhir jika elemen yang dibandingkan bernilai

sama dengan data yang dicari (mengembalikan posisi data), atau jika elemen

larik telah dibandingkan semua namun data yang dicari tidak ditemukan

(mengembalikan nilai -1).

Pada algoritma diatas idx=k+1, hal ini hanya untuk mempermudah dalam

melihat urutan, biasanya user melihat elemen pertama sebagai indeks ke - 1,

tetapi pada array elemen pertama merupakan indeks ke – 0. Maka variabel

idx untuk menyesuaikan dengan user, sedangkan variabel k menyesuaikan

dengan array.
Berikut ini adalah contoh pencarian sekuensial:

elemen	13	16	14	21	76	15
index	0	1	2	3	4	5

   Pencarian Biner

Pencarian biner adalah proses mencari data dengan membagi data atas

dua bagian secara terus menerus sampai elemen yang dicari sudah ditemukan,

atau indeks kiri lebih besar dari indeks kanan.

   Algoritma ini lebih efisien daripada algoritma pencarian sekuensial,

tetapi pencarian ini mempunyai syarat yaitu bahwa kumpulan data yang harus

dilakukan pencarian harus sudah terurut terlebih dahulu, baik terurut secara

menaik (ascendant) atau menurun (descendant). Karena data sudah terurut,

algoritma dapat menentukan apakah nilai data yang dicari berada sebelum

atau sesudah elemen larik yang sedang dibandingkan pada suatu saat. Dengan

cara ini, algoritma dapat lebih menghemat waktu pencarian.

   Pencarian dalam data terurut bermanfaat misalnya pada penyimpanan

data dengan beberapa komponen, program dapat mencari sebuah indeks

terurut. Setelah menemukan indeks yang dicari, program dapat membaca data

lain yang bersesuaian dengan indeks yang ditemukan tersebut.

Algoritma pencarian biner dengan elemen larik terurut menaik:

PROCEDURE BinSearch(input L:array[1..N] of integer, input N:integer,input X:integer, output idx : integer)

IS : Terdapat array berisi data angka terurut menaik FS : Mengembalikan posisi data yang dicari jika ketemu, dan Mengembalikan -1 jika tidak ketemu

KAMUS DATA i,j,k : integer ketemu : boolean

1 BEGIN 2 i⬅0 3 j⬅N 4 ketemu ⬅ false 5 WHILE ((!ketemu) and (i<=j)) 6 k⬅(i+j) div 2 7 IF (L[k] = X) 8 ketemu = true 9 ELSE 10 IF (L[k] < X) 11 i⬅k+1 12 ELSE 13 j⬅k-1 14 ENDIF 15 ENDIF 16 ENDWHILE 17 IF(ketemu) 18 idx⬅k+1 19 ELSE 20 idx⬅-1 21 ENDIF 22 END

  Prosedur di atas dapat bekerja pada larik yang telah terurut menaik

(ascending). Prosedur memerlukan parameter input berupa:

    ➯ L yaitu sebuah larik (array) tempat menyimpan data yang diinginkan,

    ➯ N yaitu jumlah elemen larik,

    ➯ X yaitu nilai data yang ingin dicari

serta sebuah parameter output berupa nilai idx (mengembalikan posisi nilai

jika nilai ditemukan, dan mengembalikan -1 jika nilai tidak ditemukan).

Prosedur dimulai dengan inisialisasi pencacah (i⬅0) dan menyimpan jumlah

elemen larik dalam variabel j. Variabel ketemu akan diberi nilai false, hal

ini memberitahukan bahwa data yang dicari belum ditemukan. Perulangan

diawali dengan membandingkan elemen tengah (elemen dengan indeks k)

dengan nilai data yang dicari.

➯ Jika elemen larik yang dibandingkan bernilai sama dengan data yang

     dicari, maka variabel boolean ketemu bernilai true dan prosedur

     mengembalikan nilai indeks elemen tersebut.

➯ Jika elemen larik bernilai lebih kecil dari data yang dicari, maka

     pencarian akan bergeser ke kanan dengan cara mengubah nilai i (awal

     pencacah) dengan indeks di sebelah kanan nilai tengah (i⬅k+1).

➯ Jika elemen larik bernilai lebih besar dari data yang dicari, maka

     pencarian akan bergeser ke kiri dengan cara mengubah nilai i (awal

     pencacah) dengan indeks di sebelah kiri nilai tengah (i⬅k-1).

Selanjutnya, perulangan terus dilakukan sampai ketemu bernilai true

atau nilai i>j (semua elemen larik sudah dibandingkan dengan nilai yang

dicari). Jika semua elemen larik sudah dibandingkan dengan nilai yang dicari

tetapi nilai tidak ditemukan, maka nilai ketemu akan tetap bernilai false

sehingga akan dikembalikan nilai index= -1 (penanda bahwa nilai yang dicari

tidak ditemukan dalam larik).

   Pencarian Lain
Pencarian sekuensial dan pencarian biner merupakan algoritma
pencarian dasar yang termasuk ke dalam kelompok pencarian daftar (list
search). Terdapat pula beberapa algoritma lain yang termasuk pula dalam
kelompok pencarian daftar, antara lain:
 pencarian interpolasi (interpolation search): melakukan pencarian lebih
baik daripada pencarian biner pada larik berukuran besar dengan
distribusi seimbang, tapi waktu pencariannya buruk
 pencarian Grover (Grover’s search): melakukan pencarian dalam waktu
singkat, yang merupakan pengembangan dari pencarian linier biasa pada
larik dengan elemen tidak berurut
Selain algoritma pencarian dalam kelompok pencarian daftar, terdapat
pula beberapa kelompok algoritma lain. Beberapa di antaranya adalah sebagai
berikut:

Kelompok Algoritma	Penjelasan dan Contoh Algoritma
Pencarian tanpa informasi (uninformed search)	Algoritma ini mencari data tanpa ada batasan tipe data persoalan.
Pencarian pohon (tree search)	Algoritma ini mencari data dengan bantuan struktur pohon (eksplisit maupun implisit). ⏩ breadth-first search (mencari level demi level) ⏩ depth-first search (mencari dengan meraih kedalaman pohon terlebih dahulu) ⏩ iterative-deepening search ⏩ depth-limited search ⏩ bidirectional search ⏩ uniform-cost search
Pencarian grafik (graph search)	Algoritma ini mencari data dengan algoritma penelurusuran grafik, misalnya ⏩ Djikstra’s algorithm ⏩ Kruskal’s algorithm ⏩ nearest neighbour algorithm ⏩ Prim’s algorithm
Pencarian dengan informasi (informed search)	Algoritma ini mencari data dengan fungsi heuristik yang spesifik pada persoalan tertentu. ⏩ best-first search ⏩ A*
Jenis lain	⏩ Algoritma pencarian string ⏩ Algoritma genetik ⏩ Algoritma minimax