Proses pencarian adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama (balik bertipe dasar atau bertipe bentukan )
Contoh :
Untuk mengubah (Update) data tertentu,langkah pertama yang harus dilakukan adalah mencari keberadaan data tersebut di dalam sekumpulannya.jikadata yang dicari ditemukan ,maka data tersebut dapat diubah nilainya dengan data yang baru .aktivitas awal yang sama juga dilakukan pada proses peambahan (insert)data baru.proses penambahan data dimulai dengan mencari apakah data yang akan ditambahkan sudah terdapat dalm ssekumpulan .jika sudah ada dan mengasumsikan tidak boleh ada duplikasi data maka data tersebut tidak perlu ditambahkan ,tetapi jika belum ada,maka ditambahkan.
Algortma yang paling sederhana yaitu algoritma pencarian beruntun (sequential search),dan algoritma yang sudah lebig maju yaitu pencarian bagidua (binary search)
SPESIFIKASI MASALAH PENCARIAN :
Hasil atau keluaran dari persoalan pencarian dapat bermacam-macam,bergantung pada spesifikasi rinci dari persoalan tersebut ,misalnya :
a. Pencarian hanya untuk memeriksa keberadaan x.keluaran yang diinginkan misalnya pesan (message) bahwa x ditemukan atau tidak ditemukan di dalam larik .
Contoh :
write ( ‘ditemukan !’) atau
write (‘tidak ditemukan !’)
b. Hasil pencarian adalah indeks elemen larik .jika x ditemukan maka indeks elemen larik tempat x berada diisikan ke dalam idx. Jika x tidak terdapat didalam larik L,maka idx diisi dengan harga khusus ,misalnya -1.
Contoh :
L
21 | 36 | 8 | 7 | 10 | 36 | 68 | 32 | 12 | 10 | 36 |
1 2 3 4 5 6 7 8 9 10 11
misalnya x = 68 ,maka idx = 7 ,dan bila x = 100,maka idx = -1
c. Hasil pencarian adalah sebuah nilai Boolean yang menyatakan status hasil pencarian .jika s ditemukan,maka sebuah peubah bertipe Boolean,misalnya “ketemu”,diisi dengan nilai true.sebaliknya “ketemu” diisi dengan nilai false .Hasil pencarian ini selanjutnya disimpulkan pada bagian pemanggilan prosedur .
Contoh :
Perhatikan larik L diatas !
Misalnya x = 68 ,maka ketemu = true ,dan bila x = 100,maka ketemu = false
ALGORITMA PENCARIAN BERUNTUN (SEQUENTIAL SEARCH)
Algoritma pencarian beruntun adalah proses membandingkan setiap elemen larik satu persatu secara beruntun ,mulai dari elemen pertama ,sampai elemen yang dicari ditemukan ,atau seluruh elemen sudah diperiksa.
Contoh :
1) Mencari parameter 2) Mencari jumlah datanya Jawab : 1) A = array (1…………5) of integer I,j,x : integer ; Function sequential (z : integer , N : integer) : interger Kamus data C : integer Begin C <-- 1 ; While (A [c] ! = z) AND (C <=N) C <-- C+1 ; End while If (A [c] = z) return c ; Else return -1 ; End 2) Algoritma A <-- (3,2,1,7,5) Input (x) J ß sequential (X,5) If ( J ! = -1) Output (“data ditemukan di indeks “,d); Else Output (“data tak ditemukan ) ; End |
ALGORITMA PENCARIAN BAGIDUA (BINARY SEARCH)
Algoritma ini digunakan untuk kebutuhan pencarian denagn waktu yang cepat .
Prinsip pencarian dengan membagi dua atas dua bagian mengilhami algoritma pencarian bagidua .data yang disimpan didalam larik harus sudah terurut.
contoh :
Algoritma I <-- 0 , J <-- N ,ketemu ß false While (( ! ketemu ) AND (I <= J) K <-- (I + j) div 2 If (L [k] = x) Ketemu <-- True Else if (L [K] <x) I <-- k+1 Else J <-- k-1 End if End while
N=5 X = 8 (data yang dicari) I=1 J=N J=5 While (! Ketemu )and (I<=j) 0<=5 K=1+5 div 2 =3 If (L [3] = 8) (tidak memenuhi) If (L [3] < 8) 6 < 8 I = 3+1 = 4 K= 4+5 div 2 =4 If (L [4] = x) 8 = 8 Ketemu <-- true |
ALGORITMA PENCARIAN LAIN
* Algoritma Pencarian interpolasi (interpolation search): melakukan pencarian lebih baik daripada pencarian biner pada larik berukuran besar dengan distribusi seimbang, tapi waktu pencariannya buruk.
* Algoritma Pencarian Grover (Grover’s search): melakukan pencarian dalam waktu singkat, yang merupakan pengembangan dari pencarian linier biasapada larik dengan elemen tidak berurut
* Algoritma pencarian string atau sering disebut juga pencocokan string adalah algoritma untuk melakukan pencarian semua kemunculan string pendek pattern[0..n − 1] yang disebut pattern di string yang lebih panjang teks[0..m − 1] yang disebut teks. [1]
Pencocokkan string merupakan permasalahan paling sederhana dari semua permasalahan string lainnya, dan dianggap sebagai bagian dari pemrosesan data, pengkompresian data, analisis leksikal, dan temu balik informasi. Teknik untuk menyelesaikan permasalahan pencocokkan string biasanya akan menghasilkan implikasi langsung ke aplikasi string lainnya.
* Algoritma Pencarian Adversarial
Dalam permainan seperti [[catur]], terdapat sebuah [[pohon permainan]] dari semua kemungkinan gerak dari kedua pemain dan konfigurasi hasil dari papan catur, dan kita dapat mencari pada pohon tersebut untuk menemukan strategi permainan yang efektif. Tipe permasalahan ini memiliki karakteristik unik yang mengharuskan kita memperhatikan semua kemungkinan gerak dari lawan yang mungkin terjadi. Untuk melakukannya, program permainan komputer, atau bentuk lain dari [[kecerdasan buatan]] seperti [[perencanaan mesin]], biasanya menggunakan algoritma pencarian seperti [[algoritma minimaks]], [[pemangkasan pohon pencarian]] dan [[pemangkasan alpha-beta]].
* Algoritma Pemenuhan Kendala
Ini adalah satu jenis pencarian yang memecahkan [[permasalahan pemenuhan kendala]] dimana, bukan dengan melihat sebuah jalur, solusinya adalah sebuah himpunan nilai yang diberikan pada sebuah himpunan peubah. Karena peubah-peubah dapat diproses dengan urutan apa saja, algoritma pencarian pohon biasa adalah tidak efisien. Metode pemecahan permasalahan kendala memuat [[pencarian kombinatorial]] dan [[lacak balik]], keduanya mengambil keuntungan dari kebebasan yang diasosiasikan dengan permasalahan kendala.
* Algoritma Pencarian informed
Terdapat beberapa algoritma pencarian list informed yang dikenali. Salah satu anggota dari algoritma tersebut adalah sebuah hash tabel dengan sebuah fungsi hashing, yaitu algoritma dengan heuristik yang berdasarkan pada permasalahan yang dihadapi. Sebagian besar algoritma informed adalah mengeksplore pohon. Termasuk di dalamnya adalah pencarian Breadth-first, dan A*. Sebagaimana algoritma uninformed, algoritma informed dapat dikembangkan untuk bekerja pada graf.
