Pencarian (Searching)
Proses pencarian (searching) adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama (baik bertipe dasar atau bertipe bentukan).
Pencarian terbagi Dua
1. Pencarian Internal
adalah pencarian terhadap sekumpulan
data yang disimpan di dalam memori utama
(primary memory);
2. Pencarian Eksternal
adalah pencarian terhadap sekumpulan
data yang disimpan di dalam memori
sekunder (secondary memory), seperti tape
atau disk.
Pencarian Sekuensial (Sequential Searching)
Pencarian sekuensial sering disebut pencarian linear merupakan metode pencarian
yang paling sederhana. Pencarian berurutan menggunakan prinsip sebagai berikut : data
yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data
tersebut ditemukan atau tidak ditemukan.
Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai
dengan jumlah data. Pada setiap pengulangan, dibandingkan data ke-i dengan yang
dicari. Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir
pengulangan tidak ada data yang sama, berarti data tidak ada. Pada kasus yang paling
buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
Algoritma pencarian berurutan dapat dituliskan sebagai berikut :
1 i ← 0
2 ketemu ← false
3 Selama (tidak ketemu) dan (i <= N) kerjakan baris 4
4 Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1
5 Jika (ketemu) maka i adalah indeks dari data yang dicari, jika tidak data tidak
ditemukan
Pencarian beruntun terbadi dua:
1. Pencarian beruntun pada larik tidak terurut
2. Pencarian beruntun pada larik terurut.
Pencarian beruntun pada larik
tidak terurut
Pencarian dilakukan dengan memeriksa setiap elemen larik mulai dari
elemen pertama sampai elemen yang dicari ditemukan atau sampai
seluruh elemen sudah diperiksa.
Contoh:
Misal nilai yang dicari adalah X = 21, maka elemen yang
diperiksa : 13, 16, 14, 21 (ditemukan!)
Indeks larik yang dikembalikan: IX = 4
Misal nilai yang dicari adalah X = 15, maka elemen yang
diperiksa : 13, 16, 14, 21, 76, 21 (tidak ditemukan!)
Indeks larik yang dikembalikan: IX = 0.
Pencarian Beruntun pada Larik
yang Terurut
• Jika larik sudah terurut (misal terurut
menaik, yaitu untuk setiap I=1..N, Nilai[I-
1]<Nilai[I] atau terurut mengecil, yaitu
untuk setiap I=1..N, Nilai[I-1]>Nilai[I]),
maka proses pencarian lebih singkat
dibandingkan pencarian larik yang tidak
terurut.
Pencarian Biner (Binary Search)
Salah satu syarat agar pencarian biner dapat dilakukan adalah data sudah dalam
keadaan urut. Dengan kata lain, apabila data belum dalam keadaan urut, pencarian biner
tidak dapat dilakukan. Dalam kehidupan sehari-hari, sebenarnya kita juga sering
menggunakan pencarian biner. Misalnya saat ingin mencari suatu kata dalam kamus
Prinsip dari pencarian biner dapat dijelaskan sebagai berikut : mula-mula diambil
posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus
(posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data
tengah. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama
dengan posisi tengah –1. Jika lebih besar, porses dilakukan kembali tetapi posisi awal
dianggap sama dengan posisi tengah + 1. Demikian seterusnya sampai data tengah
sama dengan yang dicari.
Untuk lebih jelasnya perhatikan contoh berikut. Misalnya ingin mencari data 17
pada sekumpulan data berikut :
3 | 9 | 11 | 12 | 15 | 17 | 20 | 23 | 31 | 35 |
Mula-mula dicari data tengah, dengan rumus (0 + 9) / 2 = 4. Berarti data tengah
adalah data ke-4, yaitu 15. Data yang dicari, yaitu 17, dibandingkan dengan data tengah
82
ini. Karena 17 > 15, berarti proses dilanjutkan tetapi kali ini posisi awal dianggap sama
dengan posisi tengah + 1 atau 5.
3 | 9 | 11 | 12 | 15 | 17 | 20 | 23 | 31 | 35 |
Data tengah yang baru didapat dengan rumus (5 + 9) / 2 = 7. Berarti data tengah
yang baru adalah data ke-7, yaitu 23. Data yang dicari yaitu 17 dibandingkan dengan
data tenah ini. Karena 17 < 23, berarti proses dilanjukkan tetapi kali ini posisi akhir
dianggap sama dengan posisi tengah – 1 atau 6.
3 | 9 | 11 | 12 | 15 | 17 | 20 | 23 | 31 | 35 |
Data tengah yang baru didapat dengan rumus (5 + 6) / 2 = 5. Berarti data tengah
yang baru adalah data ke-5, yaitu 17. data yang dicari dibandingkan dengan data tengah
ini dan ternyata sama. Jadi data ditemukan pada indeks ke-5.
Pencarian biner ini akan berakhir jika data ditemukan atau posisi awal lebih besar
daripada posisi akhir. Jika posisi sudah lebih besar daripada posisi akhir berarti data
tidak ditemukan.
Algoritma Pencarian String
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.
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.
Contoh algoritma pencocokkan string
Algoritma-algoritma pencocokkan string dapat diklasifikasikan menjadi tiga bagian menurut arah pencariannya.
Tiga kategori itu adalah :
- Dari arah yang paling alami, dari kiri ke kanan, yang merupakan arah untuk membaca, algoritma yang termasuk kategori ini adalah:
- Algoritma Brute Force
- Algoritma dari Morris dan Pratt, yang kemudian dikembangkan oleh Knuth, Morris, dan Pratt
- Dari kanan ke kiri, arah yang biasanya menghasilkan hasil terbaik secara praktikal, contohnya adalah:
- Algoritma dari Boyer dan Moore, yang kemudian banyak dikembangkan, menjadi Algoritma turbo Boyer-Moore, Algoritma tuned Boyer-Moore, dan Algoritma Zhu-Takaoka;
- Dan kategori terakhir, dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoritis, algoritma yang termasuk kategori ini adalah:
- Algoritma Colussi
- Algoritma Crochemore-Perrin
Algoritma brute force dalam pencarian string
Algoritma brute force merupakan algoritma pencocokan string yang ditulis tanpa memikirkan peningkatan performa. Algoritma ini sangat jarang dipakai dalam praktek, namun berguna dalam studi pembanding dan studi-studi lainnya.
Cara kerja
Secara sistematis, langkah-langkah yang dilakukan algoritma brute force pada saat mencocokkan string adalah:
- Algoritma brute force mulai mencocokkan pattern pada awal teks.
- Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter di teks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
- Karakter di pattern dan di teks yang dibandingkan tidak cocok (mismatch).
- Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
- Algoritma kemudian terus menggeser pattern sebesar satu ke kanan, dan mengulangi langkah ke-2 sampai pattern berada di ujung teks
Berikut adalah Algoritma brute force yang sedang bekerja mencari string:
Algoritma Brute Force
Dengan sumsi bahwa teks berada di dalam array T[1..n] dan pattern berada di dalam array P[1..m], maka algoritma brute force pencocokan string adalah sebagai berikut:
1. Mula-mula pattern P dicocokkan pada awal teks T.
2. Dengan bergerak dari kiri ke kanan, bandingkan setiap setiap karakter di dalam pattern P dengan karakter yang bersesuaian di dalam teks T sampai:
a. semua karakter yang dibandingkan cocok atau sama (pencarian berhasil), atau
b. dijumpai sebuah ketidakcocokan karakter (pencarian belum berhasil)
3. Bila pattern P belum ditemukan kecocokannya dan teks T belum habis, geser pattern P satu karakter ke kanan dan ulangi langkah 2.
Kompleksitas algoritma brute-force:
• Kompleksitas kasus terbaik adalah O(n).
• Kasus terbaik terjadi jika yaitu bila karakter pertama pattern P tidak pernah sama dengan karakter teks T yang dicocokkan .
• Pada kasus ini, jumlah perbandingan yang dilakukan paling banyak n kali
