#4. Sekilas tentang Sequential Search Sequential Search With Sentinel, Interpolation Search dan Binary Search

• Sequential Search

Pada dasarnya algoritma Pencarian Beruntun (Sequential Search) adalah proses membandingkan setiap elemen larik satu persatu secara beruntun. Pencarian beruntun dilakukan dengan melakukan penelusuran data satu persatu kemudian dicocokkan dengan data yang dicari, jika tidak sama maka penelusuran dilanjutkan, jika sama maka penelusuran dihentikan, berarti data telah ditemukan.

Sequential search dapat dilakukan pada data yang algoritmanya seperti berikut:

• larik L berisi data sebanyak n, apakah ada data x didalam larik L;


• jika ada, catat indeks dimana x ditemukan

contoh:

Perhatikan larik L dibawah ini dengan n=6 elemen

Misalkan nilai yang dicari adalah 21, berarti x=21

• Elemen yang dibandingkan(berturut-turut): 13, 16, 14, 21(ditemukan)


• Nilai 21 ditemukan pada indeks ke 4

Prosedur Pencarian berurut (Sequential Search)

Procedure SeqSearch (input L : larikInt, input n : integer, input x : integer, output ketemu : boolean)

{Mencari keberadaan nilai x di dalam larik L[1..n]}

{K.Awal: x dan larik L[1..n] sudah terdefinisi nilainya}

{K.Akhir: ketemu bernilai true jika x ditemukan. Jika x tidak ditemukan, ketemu bernilai false}

DEKLARASI

i : integer {pencatat indeks larik}

ALGORITMA

i <- 1

while (i <>

i <- i + 1

endwhile

{i = n or L[i] = x}

If L[i] = x then

ketemu <- true {x ditemukan}

else

ketemu <- false {x tidak ada didalam larik}

endif

• Sequential Search with Sentinel

Sequential Search with Sentilnel adalah elemen fiktif yang sengaja ditambahkan sesudah elemen terakhir larik.

Perhatikan array data berikut :

Terdapat 6 buah data dalam array (dari indeks 0 s/d 5) dan terdapat 1 indeks array tambahan (indeks ke 6) yang belum berisi data (disebut sentinel).

Array pada indeks ke 6 berguna untuk menjaga agar indeks data berada pada indeks 0 s/d 5 saja. Bila pencarian data sudah mencapai array indeks yang ke-6 maka berarti data TIDAK ADA, sedangkan jika pencarian tidak mencapai indeks ke-6, maka data ADA.

Analisa Algoritma :

• Sebelumnya setiap pemeriksaan apakah x=l[i], selalu didahului oleh pemeriksaan apakah i<=n


• Pemeriksaan i<=n dapat dihilangkan, asal dijamin bahwa pasti ditemukan data x didalam larik l.


• Untuk itu pada elemen larik ke n+1 dimasukkan x sebagai sentinel (sehingga i tidak melewati batas akhir larik)


• Jika data x ditemukan pada indeks n+1, berarti bahwa x tidak ada didalam larik l, dan jika x ditemukan pada indeks selain n+1, berarti x ditemukan

• Interpolation Search

Interpolation search sering juga disebut sebagai pencarian ekstrapolasi yaitu algoritma untuk mencari nilai kunci yang diberikan dalam array di indeks yang telah diperintahkan oleh nilai-nilai kunci.

Pada metode pencarian ini, kita mencoba menebak letak data yang kita cari, dengan perhitungan

• Jika data[posisi] > data yg dicari, high = pos – 1


• Jika data[posisi] < low =" pos">

• Pencarian Bagi Dua (Binary Search)

Pencarian bagi dua atau binary search hanya bisa dilakukan pada data yang sudah terurut. Pencarian bagidua atau pencarian biner adalah metode pencarian yang diterapkan pada sekumpulan data yang sudah terurut (terurut menaik atau terurut menurun). Salah satu keuntungan data terurut adalah memudahkan pencarian, dalam hal ini pencarian bagidua.

Pencarian Biner (Binary Search) dilakukan untuk :

1. memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.


2. Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).


3. Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Langkah-Langkah dalam melakukan pencarian dengan binary search yaitu:

Contoh :

Terdapat sebuah array yang berisi angka-angka seperti dibawah ini:

Dicari angka 89, maka prosesnya:

Bahasa Algoritma

Untuk Contoh Program Silakan Download Di Sini