“Sequential search atau Pencarian sekuensial” bisa disebut dengan pencarian linear yang merupakan model pencarian yang paling simpel dan sederhana banget deh yang dapat dilakukan terhadap suatu kumpulan data. Suatu tekhnik pencarian dalam array (1 dimensi) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu.
Biar kalian lebih paham secara konsep, penjelasannya adalah sebagai berikut :
Keunggulan dari pencarian sekuensial ini adalah jika data yang dicari terletak di indeks array terdepan maka waktu dalam pencarian nya sangat cepat, dalam artian waktu yang minim sekali. Keburukannya adalah kalau jika data indeks array nya yang dicari paling belakang, maka waktu yang dicari tuh lama banget (maksimal).
Terdapat L yang merupakan larik yang berisi n buah data ( L[0],L[1]…….L[n-1]) dan k adalah data yang akan dicari. Pencarian dilakukan untuk menemukan L[i] = k dengan i adalah bilangan indeks terkecil yang memenuhi kondisi 0<= k <=n-1. Tentu saja bahwa data yang di cari tidak ditemukan.
Jika misalnya terdapat angka 4, maka ditulis ada, sedangkan jika dimunculkan angka 6, namun angka 6 tidak ada maka akan muncul tulisan tidak ada.
Berikut merupakan program yang telah dibuat sebelumnya :
L = {4,12,9,-2,12,7,1,100}
Tahukah kamu dimana posisi 12 yang pertama ?
Nah, dalam hal ini k adalah 12 dan k ditemukan berupa indeks 2. Angka 12 yang pertama akan dipilih oleh program, karena secara logika angka 12 merupakan data yang pertama muncul. Coba deh kamu bayangin aja misalnya dalam antrian, orang yang mengantri di depan akan duluan mendapatkan giliran.
Berikut merupakan contoh program Pencarian Sekuensial (Sequential Search):
//Sequential searching
#include
#include
void main()
{
clrscr();
int data[8] = {4,12,9,-2,12,7,1,100};
int cari,index;
int ketemu=0;
cout<<”masukkan data yang ingin dicari = “;
cin>>cari;
for(int i=0;i<8;i++)
{
if(data[i] == cari)
{
ketemu=1;
index = i;
break;
}
}
if(ketemu == 1)
{
cout<<”Data ada!”<cout<<”Data terletak di index ke – “<}
else cout<<”Data Tidak ada!”<getch();
}
tampilannya jika program ini dijalankan :
Pencarian terhadap data urut “ Pencarian Binari ( Binary Search)” :
“Pencarian Sekuensial” akan memakan banyak waktumu apabila mencari data indeks array yang paling akhir dan ditambah lagi kalau datanya tu banyak banget Apalagi kumpulan data udah dalam keadaan urut, Untuk mengatasi masalah ini dan untuk menyingkat waktu terdapat algoritma yang dirancang agar pencarian data dilakukan secara efesien. Metode yang digunakan dikenal dengan sebutan “pencarian biner atau binary search”. Metode ini merupakan tekhnik pencarian data dalam dengan cara membagi dua bagian setiap kali terjadi proses pengurutan.
Data yang dicari harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian. Pencarian biner dilakukan dengan membagi larik menjadi dua bagian dengan jumlah yang sama besar atau berbeda 1 jika jumlah data semula ganjil. Data yang dicari kemudian dibandingkan dengan data terakhir pada bagian pertama, jika lebih besar dari data tengah maka akan diulang dari awal dengan +1, jika lebih kecil maka sebaliknya, dari data tengah maka -1. Dalam hal ini ada empat kemungkinan yang terjadi yaitu :
1. Data yang dicari sama dengan elemen terakhir pada bagian pertama dalam larik. Jika kondisi ini terpenuhi, data yang dicari berarti ditemukan. Data dicari dari posisi satu sampai posisi akhir N. jika tidak diketemukan maka data akan terus mencari sampai menemukan data yang sama.
2. Data yang dicari bernilai kurang dari nilai elemen terakhir pada bagian pertama dalam lari. Pada keadaan ini, pencarian diteruskan pada bagian pertama.
3. Data yang dicari bernilai lebih dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian kedua.
4. Pada pengurutan biner, data akan dibandingkan dengan data yang ditengahnya, data tengah dicari dengan menjumlahkan posisi awal dengan posisi akhir kemudian hasil jumlah data tersebut dibagi menjadi 2. Data tersebut akan dibandingkan dengan data yang ditengah apakah akan lebih besar atau lebih kecil.
Berikut merupakan contoh program Pencarian Binari ( Binary search) :
//Pencarian Binari
#include
#include
int data[10] = {1,3,4,7,12,25,40,65,78,90}; //variabel global
int binary_search(int cari)
{
int l,r,m;
int n = 10;
l = 0;
r = n-1;
int ketemu = 0;
while(l<=r && ketemu==0)
{
m = (l+r)/2;
if( data[m] == cari )
ketemu = 1;
else
if (cari < data[m])
r = m-1;
else l = m+1;
}
if(ketemu == 1) return 1; else return 0;
}
void main()
{
clrscr();
int cari,hasil;
cout<<”masukkan data yang ingin dicari = “;
cin>>cari;
hasil = binary_search(cari);
if(hasil == 1)
{
cout<<”Data ada!”<}
else
if(hasil == 0)
cout<<”Data Tidak ada!”<getch();
}
Berikut contoh program yang udah di jalankan:
Algoritma Pencarian String
- Pencarian string di dalam teks disebut juga pencocokan string (string matching atau pattern matching).
- Persoalan pencarian string dirumuskan sebagai berikut:
1. teks (text), yaitu (long) string yang panjangnya n karakter
2. pattern, yaitu string dengan panjang m karakter (m < n) yang akan dicari di dalam teks.
Carilah (find atau locate) lokasi pertama di dalam teks yang bersesuaian dengan pattern. Aplikasi dari masalah pencocokan string antara lain pencarian suatu kata di dalam dokumen (misalnya menu Find di dalam Microsoft Word).
Contoh 10.1:
Pattern: hari
Teks: kami pulang hari kamis
Ý target
Contoh 10.2:
Pattern: not
Teks: nobody noticed him
Ý target
Contoh 10.3:
Pattern: apa
Teks: Siapa yang menjemput Papa
dari kota Balikpapan?
10.1 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.
Contoh 10.3:
Teks: nobody noticed him
Pattern: not
nobody noticed him
s=0 not
s=1 not
s=2 not
s=3 not
s=4 not
s=5 not
s=6 not
s=7 not
Contoh 10.4:
Teks: 10010101001011110101010001
Pattern: 001011
10010101001011110101010001
s=0 001011
s=1 001011
s=2 001011
s=3 001011
s=4 001011
s=5 001011
s=6 001011
s=7 001011
s=8 001011
Pseudo-code algoritmanya:
| procedure BruteForceSearch(input m, n : integer, input P : array[1..m] of char, input T : array[1..n] of char, output idx : integer) { Mencari kecocokan pattern P di dalam teks T. Jika ditemukan P di dalam T, lokasi awal kecocokan disimpan di dalam peubah idx. Masukan: pattern P yang panjangnya m dan teks T yang panjangnya n. Teks T direpresentasika sebagai string (array of character) Keluaran: posisi awal kecocokan (idx). Jika P tidak ditemukan, idx = -1. } Deklarasi s, j : integer ketemu : boolean Algoritma: s¬0 ketemu¬false while (s £ n-m) and (not ketemu) do j¬1 while (j £ m) and (P[j] = T[s+j]) do j¬j+1 endwhile { j > m or P[j] ¹ T[s+j] } if j = m then { kecocokan string ditemukan } ketemu¬true else s¬s+1 { geser pattern satu karakter ke kanan teks } endif endfor { s > n – m or ketemu } if ketemu then idx¬s+1 { catatan: jika indeks array dimulai dari 0, idx ¬ s } else idx¬-1 endif |
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 misalnya:
Teks: Ini adalah string panjang yang berakhir dengan zz
Pattern: zz
Kasus terburuk membutuhkan m(n – m + 1) perbandingan, yang mana kompleksitasnya adalah O(mn), misalnya:
Teks: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
Pattern: aaaab
10.2 Algoritma Knuth-Morris-Pratt (KMP)
Pada algoritma brute force, setiap kali ditemukan ketidakcocokan pattern dengan teks, maka pattern digeser satu karakter ke kanan.
Sedangkan pada algoritma KMP, kita memelihara informasi yang digunakan untuk melakukan jumlah pergeseran. Algoritma menggunakan informasi tesrebut untuk membuat pergeseran yang lebih jauh, tidak hanya satu karakter seperti pada algoritma brute force.
Dengan algoritma KMP ini, waktu pencarian dapat dikurangi secara signifikan. Algoritma KMP dikembangkan oleh D. E. Knuth, bersama-sama dengan J. H. Morris dan V. R. Pratt.
1 2 3 4 5 6 7 8 9…
Teks: bimbingan belajar atau bimbel
Pattern: bimbel
j = 5
1 2 3 4 5 6 7 8 9…
Teks: bimbingan belajar atau bimbel
Pattern: bimbel
j = 2
Definisi:
Misalkan A adalah alfabet dan x = x1x2…xk , k Î N, adalah string yang panjangnya k yang dibentuk dari karakter-karakter di dalam alfabet A.
Awalan (prefix) dari x adalah upa-string (substring) u dengan
u = x1x2…xk – 1 , k Î {1, 2, …, k – 1}
dengan kata lain, x diawali dengan u.
Akhiran (suffix) dari x adalah upa-string (substring) u dengan
u = xk – b xk – b + 1 …xk , k Î {1, 2, …, k – 1}
dengan kata lain, x diakhiri dengan v.
Pinggiran (border) dari x adalah upa-string r sedemikian sehingga
r = x1x2…xk – 1 dan u = xk – b xk – b + 1 …xk , k Î {1, 2, …, k – 1}
dengan kata lain, pinggiran dari x adalah upa-string yang keduanya awalan dan juga akhiran sebenarnya dari x.
Contoh 10.5. Misalkan x = abacab. Awalan sebenarnya dari x adalah
, a, ab, aba, abac, abaca
(ket: = string kosong)
Akhiran sebenarnya dari x adalah
, b, ab, cab, acab, bacab
Pinggiran dari x adalah
, ab
Pinggiran mempunyai panjang 0, pinggiran ab mempunyai panjang 2.
Fungsi Pinggiran (Border Function)
Fungsi pinggiran b(j) didefinisikan sebagai ukuran awalan terpanjang dari P yang merupakan akhiran dari P[1..j].
Sebagai contoh, tinjau pattern P = ababaa. Nilai F untuk setiap karakter di dalam P adalah sebagai berikut:
| j | 1 | 2 | 3 | 4 | 5 | 6 | |
| P[j] | a | b | a | b | a | a | |
| b(j) | 0 | 0 | 1 | 2 | 3 | 1 |
| procedure HitungPinggiran(input m : integer, P : array[1..m] of char, output b : array[1..m] of integer) { Menghitung nilai b[1..m] untuk pattern P[1..m] } Deklarasi k,q : integer Algoritma: b[1]¬0 q¬2 k¬0 for q¬2 to m do while ((k > 0) and (P[q] ¹ P[k+1])) do k¬b[k] endwhile if P[q]=P[k+1] then k¬k+1 endif b[q]=k endfor |
Teks: abcabcabd
Pattern: abcabd
Mula-mula kita hitung fungsi pinggiran untuk pattern tersebut:
| j | 1 | 2 | 3 | 4 | 5 | 6 | |
| P[j] | a | b | c | a | b | d | |
| b(j) | 0 | 0 | 0 | 1 | 2 | 0 |
Pattern: abcabd
j = 3
Algoritma KMP selengkapnya adalah:
| procedure KMPsearch(input m, n : integer, input P : array[1..m] of char, input T : array[1..n] of char, output idx : integer) { Mencari kecocokan pattern P di dalam teks T dengan algoritma Knuth-Morris-Pratt. Jika ditemukan P di dalam T, lokasi awal kecocokan disimpan di dalam peubah idx. Masukan: pattern P yang panjangnya m dan teks T yang panjangnya n. Teks T direpresentasika sebagai string (array of character) Keluaran: posisi awal kecocokan (idx). Jika P tidak ditemukan, idx = -1. } Deklarasi i, j : integer ketemu : boolean b : array[1..m] of integer procedure HitungPinggiran(input m : integer, P : array[1..m] of char, output b : array[1..m] of integer) { Menghitung nilai b[1..m] untuk pattern P[1..m] } Algoritma: HitungPinggiran(m, P, b) j¬0 i¬1 ketemu¬false while (i £ n and not ketemu) do while((j > 0) and (P[j+1]¹T[i])) do j¬b[j] endwhile if P[j+1]=T[i] then j¬j+1 endif if j = m then ketemu¬true else i¬i+1 endif endwhile if ketemu then idx¬i-m+1 { catatan: jika indeks array dimulai dari 0, maka idx¬i-m } else idx¬-1 endif |
