Algoritma Searching

Searching

Searching (pencarian) merupakan proses yang fundamental dalam pengolahan data. Proses pencarian adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe data sama (baik bertipe dasar atau bertipe bentukan sebagai contoh untuk melakukan update (perubahan) data tertentu, langkah awal yang harus dilakukan adalah dengan menemukan keberadaan data tersebuta didalam kumpulannya. Jika data yang dicari ditemukan, maka data tersebut dapat di ubah nilainya dengan data yang baru.Algoritma sequential search (pencarian beruntun)

Algoritma pencarian yang paling sederhana adalah metode sequential search atau dapat disebut juga dengan linear search (pencarian lurus). Pada dasarnya algoritma ini dalam prosenya yaitu melakukan pencarian dengan membandingkan setiap elemen larik satu persatu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan, atau seluruh elemen telah diperiksa.

Sebagai contoh dapat dilihat pada larik L dibawah ini

1. Misalkan nilai yang dicari adalah : x = 21, Elemen yang dibandingkan berturut-turut : 13,16,14,21 (ditemukan!), Indeks larik yang dikembalikan : idx = 4
2. Misalkan nilai yang dicari adalah : x = 13, Elemen yang dibandingkan berturut-turut : 13 (ditemukan!), Indeks larik yang dikembalikan : idx = 1
3. Misalkan nilai yang dicari adalah : x = 15, Elemen yang dibandingkan berturut-turut : 13, 16, 14, 21, 76, 21 (tidak ditemukan!)I,ndeks larik yang dikembalikan : idx = -1

Terdapat dua golongan sequential search

1. Sequential search tanpa boolean
2. Tanpa sentinel
3. Dengan sentinel
4. Sequential search dengan boolean

Algoritma sequential search tanpa boolean tanpa sentinel

Misalkan diberikan data sebagai berikut :

5	1	9	4	2
1	2	3	4	5

Data yang dicari : 9

• Angka 1 = 9 ? F
• Angka 2 = 9 ? F
• Angka 3 = 9 ? T

Maka data yang dicari ditemukan pada indeks ke -3

berikut ini adalah pseudo code dari Algoritma sequential search tanpa boolean tanpa sentinel.

Algoritma sequential search tanpa boolean dengan sentinel

Misalkan diberikan data sebagai berikut :

Data yang dicari : 9

• Tempatkan data yang dicari pada sentinel.
• Telusuri array seperti sequential search tanpa sentinel, jika data ditemukan pada sentinel, maka data yang dicari tidak ada/tidak ditemukan, tapi jika data yang dicari ditemukan bukan pada sentinel, maka data yang dicari ditemukan.

Berikut ini adalah pseudo code dari algoritma sequential search dengan sentinel

Algoritma sequential search dengan boolean

Misalkan diberikan data sebagai berikut :

5	1	9	4	2
1	2	3	4	5

Data yang dicari : 9

Proses pencariannya sama seperti proses pencarian pada metode sequential search lainnya, hanya saja melibatkan sebuah variabel lain yg bertipe boolean.

Berikut ini adalah pseudo code dari algoritma sequential search dengan boolean.

Secara umum algoritma pencarian beruntun berjalan lambat. Waktu pencarian sebanding dengan jumlah elemen larik. Misalkan larik berukuran N elemen. Maka, pada kasus dimana x terdapat didalam larik atau x ditemukan pada elemen yang terakhir, kita harus melakukan perbandingan seluruh elemen larik, yang berarti jumlah perbandingan yang terjadi sebanyak N kali. Dengan kata lain waktu pencarian dengan algoritma ini sebanding dengan N. Bayangkan bila larik berukuran 100.000 buah elemen, maka kita harus melakukan perbandingan sebanyak 100.000 buah elemen. Andaikan satu operasi perbandingan membutuhkan waktu 0,01 detik, maka untuk 100.000 buah perbandingan diperlukan waktu sebesar 1000 detik atau 16,7 menit. Jadi dapat diambil kesimpulan bahwa algoritma ini tidak cocok untuk diterapkan pada data bervolume besar.

Algoritma Binary Search (Pencarian bagi dua)

Pencarian data yang terurut menunjukkan kinerja yang lebih baik daripada pencarian pada data yang belum terurut. Terdapat algoritma pencarian pada data terurut yang paling efisien, yaitu algoritma binary search (pencarian bagidua). Algoritma ini digunakan untuk kebutuhan pencarian data dengan waktu yang cepat. Prinsip kerja algoritma ini dengan membagi larik  menjadi dua bagian (bagian kiri dan bagian kanan), dan mengecek data di posisi tengah apakah sama atau tidak dengan data yang dicari, jika tidak prose pencarian akan dilanjutkan ke larik bagian kiri atau bagian kanan. Data yang disimpan didalam larik harus sudah terurut. Untuk memudahkan pembahasan, selanjutnya kita misalkan elemen larik sudah terurut menaik. Dalam proses pencarian, kita memerlukan dua buah indeks larik, yaitu indeks terkecil dan indeks terbesar. Kita menyebut indeks terkecil sebagai indeks ujung kiri larik dan indeks terbesar sebagai indeks ujung kanan. Istilah kiri dan kanan dinyatakan dengan membayangkan elemen larik terntang secara horizontal.

Misalkan diberikan data sebagai berikut :

3	7	12	15	29
1	2	3	4	5

Data yang dicari : 7

1. Bagi larik menjadi dua bagian untuk mencari posisi tengah (k) dengan cara indeks atas (Ia) dijumlahkan dengan indeks bawah (Ib) lalu dibagi dua.

K = (Ia + Ib ) div 2

= (1 + 5) div 2

= 3

2. Periksa data di posisi tengah larik (12), lalu bandingkan apakah sama atau tidak(12 = 7? F), karena tidak sama maka akan diperiksa apakah data di posisi tengah lebih kecil dari data yang dicari (12 < 7 ? F) karena lebih besar maka pencarian dilanjutkan ke bagian kiri dengan cara menarik Indeks bawah ke kiri (Ib = k – 1).

Hitung kembali titik tengah dari larik yang ditinjau (didapat k =1)

3. ulangi langkah 1 s/d langkah 2 sampai data ditemukan atau sampai harga Ia > Ib.

Angka 7 ditemukan pada indeks ke-2, dan pada looping ke-3.

Berikut ini adalah pseudo code dari algoritma binary search.

Kedua algoritma pencarian diatas mempunyai kelebihan dan kekurangan masing-masing. Algortima pancarian beruntun dapat digunakan baik untuk data yang belum terurut maupun untuk data yang sudah terurut. Sebaliknya, algoritma pencarian bagidua hanya dapat digunakan untuk data yang sudah terurut saja.

Ditinjau dari kinerja pencarian, kita sudah mengetahui bahwa untuk kasus terburuk ( yaitu jika pencarian gagal menemukan x), algoritma pencariann beruntun memerlukan waktu yang sebanding dengan n (banyaknya data), sedangkan algortima pencarian bagidua membutuhkan waktu yang sebanding dengan 2log(n). Karena 2log(n) < n untuk n >1, maka jika n semakin besar waktu pencarian dengan algoritma bagidua jauh lebih sedikit daripada waktu pencarian dengan algoritma pencarian beruntun.

Sebagai perbandingan antara algoritma pencarian beruntun dengan algoritma pencarian bagidua, tinjaulah kasus dimana x tidak ditemukan di dalam larik yang sudah terurut misalkan :

1. Untuk larik yag berukuran n = 256 elemen

• algoritma pencarian beruntun melakukan pembandingan elemen larik sebanyak 256 kali,
• algoritma pencarian bagidua melakukan pembandinga sebanyak 2log(256) = 8 kali.

2. Untuk larik yang berukuran n = 1024 elemen

• algoritma pencarian beruntun melakukan pembandingan elemen larik sebanyak 1024 kali,
• algoritma pencarian bagidua melakukan pembandinga sebanyak 2log(1024) = 10 kali.

A. Jenis-jenis Searching

1.       Sequential search
Disebut juga sebagai metode pencarian urut adalah metode pencarian yang paling mudah. Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana data-data tidak perlu diurutkan terlebih dahulu. Kemungkinan terbaik (best case) adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat sebentar (minimal). Sedangkan kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal).

Sequential search memiliki proses sebagai berikut:

»     Tentukan banyaknya data yang akan di olah, misal banyak data adalah N.

»     Tentukan data apa yang akan dicari, misal data yang akan dicari adalah C.

»     Deklarasikan sebuah counter untuk menghitung banyak data yang ditemukan, missal counternya adalah K.

»     Inisialisasikan K =0

»     Lakukanlah perulangan sebanyak N kali

»     Dalam tiap proses perulangan tersebut periksalah apakah data yang sedang diolah sama dengan data yang dicari.

»     Jika ternyata sama K=K+1

»     Jika tidak, lanjutkan proses perulangan .

»     Setelah proses perulangan berhenti, periksalah nilai K.

»     Jika nilai K lebih dari 0, artinya data yang dicari ada dalam data /array dan tampilkan   nilai K ke layer sebagai jumlah data yang ditemukan.

»     Jika nilai K=0, artinya data yang dicari tidak ditemukan dalam data / array dan tampilkan ke layar bahwa data tidak ditemukan

»     Proses selesai.
Dapat disimpulkan bahwa sequential search, akan mencari data dengan cara membandingkannya satu-persatu dengan data yang ada. Prosesnya tentu saja akan singkat jika data yang diolah sedikit, dan akan lama jika data yang diolah banyak. Disarankan proses ini digunakan pada jumlah data yang sedikit saja.

1.       Binary Search.
Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu. Jika terdapat N buah data yang akan diolah, data yang dicari akan dibandingkan dengan data ke-N jika data ke-N lebih besar dari data yang dicari maka akan dilakukan pembagian data menjadi dua bagian. Kemudian ujung data pada setiap bagian dibandingkan lagi dengan nilai yang akan dicari.

2.       Interpolation Search
Proses pencarian data ini hampir sama dengan proses pencarian binary search, pencarian ini juga dilakukan pada kumpulan data yang sudah urut. Akan tetapi jika pada binary search kita membagi data menjadi 2 bagian tiap prosesnya, pada interpolation search kita akan membagi data menurut rumus sebagai berikut:

Posisi = ( kunci – data[low] / data[high] – data[low] ) * ( high – low ) + low

Singkatnya proses pencarian interpolation search hampir mirip dengan proses pencarian kata dikamus, yaitu kita mencari data yang dimaksud dengan cara memperkirakan letak data. 

Referensi:

• Munir,Rinaldi, Algoritma dan Pemrograman dalam bahasa Pascal dan C Edisi Revisi,Informatika Bandung, 2011.
• Tim Algoritma dan Pemrograman UNIKOM Indonesia, Algoritma dan Pemrograman Searching,Unikom, Tim Algoritma dan Pemrograman UNIKOM Indonesia, 2015.