Pencarian...

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 :

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

ini. Karena 17 > 15, berarti proses dilanjutkan tetapi kali ini posisi awal dianggap sama

dengan posisi tengah + 1 atau 5.

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.

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

Pencarian...

Contoh algoritma pencocokkan string

Algoritma brute force dalam pencarian string

Cara kerja

Share this:

0 komentar:

Posting Komentar