ALGORITMA PENCARIAN

PENCARIAN SEKUENSIAL

       Pencarian sekuensial adalah proses membandigkan setiap elemen larik (array) satu per satu dengan nilai yang dicari secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau sampai seluruh elemen sudah di periksa.

Algoritma sekuensial ini cocok untuk pencarian nilai tertentu pada sekumpulan data terurut maupun tidak terurut. Algoritma sekuensial merupakan algoritma yang cepat dan sederhana karena tidak memerlukan proses persiapan data atau pengurutan data.

Logikanya Algoritma sekuensial ini adalah, bahwa dia akan mencari terus-menerus nilai sampai akhir, misalkan ada 10 pintu dan diantara pintu-pintu tersebut sebuah nilai tersimpan, bila nilai tersimpan pada pintu pertama, otomatis dengan cepat kita langsung dapat menemukan nilai tersebut karena langkah awalnya untuk melakukan pencarian pada pintu-pintu tersebut, logikanya kita pasti akan membuka pintu pertama, dan saat sebuah nilai tersimpan disitu ya kita langsung menemukannya.

Kemudian jika nilai tersebut tersimpan pada pintu ke 5 artinya kita harus melewati pintu ke-1, 2, 3, 4 dan setelah itu pada saat kita membuka pintu yang ke 5, barulah kita bisa menemukan nilai yang tersimpan tersebut. Namun bila nilai tersimpan pada pintu terakhir atau pintu ke 10 (dalam contoh ini) maka kita harus melakukan beberapa langkah membuka pintu-pintu sebelumnya untuk menuju ke pintu terakhir.

Kelebihan algoritma sekuensial adalah begitu cepat dalam mencari sebuah nilai dari sekumpulan kecil data. Namun kelemahannya adalah algoritma ini akan bekerja begitu lama sekali dalam mencari sebuah nilai jika nilai tersebut terletak di akhir dari sekumpulan data yang begitu banyak.

Contoh Algoritma pencarian sekuensial:
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
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.
• idx yaitu yang akan mengembalikan posisi ditemukannya data yan g dicari apabila ketemu dan akan mengembalikan nilai -1 jika data tidak ditemukan.

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 biner ini lebih efisien daripada algoritma sekuensial, tetapi pencarian ini mempunyai syarat yaitu bahwa kumpulan data yang akan dilakukan pencarian harus sudah terurut terlebih dahulu, baik terurut secara meningkat maupun terurut secara menurun. Kemudian jika data sudah terurut, maka algoritma dapat menentukan apakah nilai data yang dicari berada sebelum atau sesudah elemen larik yang sedang dibandingkan. Dengan cara ini algoritma dapat lebih menghemat waktu pencarian.

Pencarian pada data terurut akan lebih cepat, misalnya meskipun kita menyimpan data dengan beberapa komponen yang begitu banyak, program akan tetap dapat mencari data melalui sebuah indeks terurut. Kemudian setelah menemukan indeks yang dicari, maka program akan dapat membaca data lain yang bersesuaian dengan indeks yang ditemukan tersebut.

• Jika elemen larik lebih kecil dari data yang dicari, maka pencarian akan bergeser kekanan dengan cara mengubah nilai awal pencacah dengan indeks disebelah kanan nilai tengah.

•  Jika elemen larik lebih besar dari data yang dicari, maka pencarian akan bergeser kekiri dengan cara mengubah nilai awal pencacah dengan indeks disebelah kiri nilai tengah.

Contoh Algoritma pencarian biner dengan elemen larik menaik:

Kamus Data

i, j, k : integer

ketemu : boolean

BEGIN

i <- 0

j <- 0

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

ENDIF

ENDIF

ENDWHILE

IF ( ketemu)

idx <- k+1

ELSE

idx <- -1

ENDIF

END

       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.

Contoh algoritma pencarian biner dengan elemen menurun:

Kamus Data

i, j, k : integer

ketemu : boolean
BEGIN
i <- 0
j <- 0
ketemu <- false
WHILE ( ( !ketemu) and ( i <= j))
k <- ( i + j ) div 2
IF ( L[k] = X )
ketemu = true
ELSE
IF ( L[k] < X )
j <- k-1
ELSE
i <- k+1
ENDIF
ENDIF
ENDWHILE
IF (ketemu)
idx <- k+1
ELSE
idx <- -1
ENDIF
END

PENCARIAN STRING

       Pencarian string atau sering disebut juga pencocokkan string adalah algoritma untuk melakukan pencarian semua kemunculan string pendek pattern[0..n-1] yang disebut pattern string, kemudian 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-alforitma pencocokkan string dapat diklasifikasikan menjadi 3 bagian menurut arah pencariannya :

• Dari arah yang paling alami, dari kiri ke kanan, yang merupakan arah untuk membaca.
• Dari arah kanan ke kiri, arah yang biasanya menghasilkan hasil terbaik secara partikal.
• Dan kategori terakhir, dari arah yang ditentukan secara spesifik oleh algoritma tersebut, arah ini menghasilkan hasil terbaik secara teoritis

 Algoritma Brute Force dalam Pencarian String

       Algoritma Brute Force merupakan algoritma pencocokkan 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 adlah :

1. Algoritma brute force mulai mencocokkan pattern awal teks.
2. Dari kiri ke kanan, algoritma ini akan mencocokkan karakter per karakter pattern dengan karakter diteks yang bersesuaian, sampai salah satu kondisi berikut dipenuhi:
1. Katarkter di pattern dan di teks yang di bandingkan tidak cocok (mismatch).
2. Semua karakter di pattern cocok. Kemudian algoritma akan memberitahukan penemuan di posisi ini.
3. Algoritma kemudian terus menggeser pattern sebesar satu kekanan, dan mengulangi langkah ke-2 sampai pattern berada diujung teks.

Contoh (Pseudocode)
Pseudocode dalam algoritma brute force ini:

procedure BruteForeceSearch(
input m, n : integer
input p     : array [0..n-1] of char,
input T     : array [0..m-1] of char,
outout ketemu : array [100..m-1] of boolean

Deklarasi :
i,j            : integer

algoritma :
for ( i:=0 to m-n) do
j:=0
while (j < n and T(i+j) = p[j] ) do
j := j+1
endwhile
if (j >= n) then
ketemu [i] := true
end if
endfor