All About Searching

Pencarian (searching) merupakan proses yang fundamental dalam pengolahan data. Proses pencarian adalah menemukan nilai (data) tertentu di dalam sekumpulan data yang bertipe sama (baik bertipe dasar atau bertipe bentukan). Sebagai contoh, untuk mengubah (update) data tertentu, langkah pertama yang harus dilakukan adalah mencari keberadaan data tersebut di dalam kumpulannya. Jika data yang dicari ditemukan, maka data tersebut dapat diubah nilainya dengan data yang baru. Aktivitas awal yang samajuga dilakukan dalam proses penambahan (insert) data baru. Proses penambahan data dimulai dengan mencari apakah data yang akan ditambahkan sudah terdapat di dalam kumpulan. Jika sudah adaa dan mengasumsikan tidak boleh ada duplikasi data maka data tersebut tidak perlu ditambahkan, tetapi jika belum ada, maka tambahkan.

1.      ALGORITMA PENCARIAN BERUNTUN (Sequential Search)

          Pada dasarnya, algoritma pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama, sampai elemen yang dicari ditemukan, atau seluruh elemen sudah diperiksa.

            Misalnya terdapat array satu dimensi sebagai berikut:

indeks	0	1	2	3	4	5	6	7
value	8	10	6	-2	11	7	1	100

                        Kemudian program akan meminta data yang akan dicari, misalnya 6. Jika ada maka akan ditampilkan tulisan “ADA”, sedangkan jika tidak ada maka akan ditampilkan tulisan “TIDAK ADA”.

 

1.      ALGORITMA PENCARIAN BAGI DUA (Binary Search)

            Terdapat algoritmaa pencariaan pada data terurut yang paling mangkus (efficient), yaitu algoritma pencarian bagi dua atau pencarian biner (binary search). Algoritma ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Sebenarnya, dalam kehidupan sehari-hari kita sering menerapkan pencarian bagi dua. Untuk mencari arti kata tertentu di dalam kamus (misalnya kamus bahasa Inggris), kita tidak membuka kamus itu dari halaman awal sampai halaman akhir satu per satu, namun kita mencarinya dengan cara membelah atau membagi dua buku itu. Jika kata yang dicari tidak terletak di halaman pertengahan itu, kita mencari lagi di belahan bagian kiri atau belahan bagian kanan dengan cara membagi dua belahan yang dimaksud. Begitu seterusnya sampai kata yang dicari ditemukan. Hal ini hanya bisa dilakukan jika kata-kata di dalam kamus sudah terurut.

Prinsip pencarian biner adalah:

·         Data diambil dari posisi 1 sampai posisi akhir N

·         Kemudian cari posisi data tengah dengan rumus: (posisi awal + posisi akhir) / 2

·          Kemudian data yang dicari dibandingkan dengan data yang di tengah, apakah sama atau lebih kecil, atau lebih besar?

·         Jika lebih besar, maka proses pencarian dicari dengan posisi awal adalah posisi tengah + 1

·         Jika lebih kecil, maka proses pencarian dicari dengan posisi akhir adalah posisi tengah – 1

·         Jika data sama, berarti ketemu.

Contoh Data:

Misalnya data yang dicari 17

0	1	2	3	4	5	6	7	8
3	9	11	12	15	17	23	31	35
A				B				C

Karena 17 > 15 (data tengah), maka: awal = tengah + 1

0	1	2	3	4	5	6	7	8
3	9	11	12	15	17	23	31	35
					A	B		C

Karena 17 < 23 (data tengah), maka: akhir = tengah – 1

0	1	2	3	4	5	6	7	8
3	9	11	12	15	17	23	31	35
					A=B=C

Karena 17 = 17 (data tengah), maka KETEMU!

1.     INTERPOLATIOM 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.

Misal terdapat data sebagai berikut:

Kode                     Judul                                                 Buku Pengarang

025                       The C++ Programming           James Wood

034                       Mastering Delphi 6                 Marcopolo

041                       Professional C#                      Simon Webe

056                       Pure JavaScript v2                  Michael Bolton

063                       Advanced JSP & Servlet        David Dunn

072                       Calculus Make it Easy            Gunner Christian

088                       Visual Basic 2005 Express      Antonie

096                       Artificial Life : Volume 1       Gloria Virginia

Kunci Pencarian ? 088

Low ? 0

High ? 7

Posisi = (088 - 025) / (096 - 025) * (7 - 0) + 0 = [6]

Kunci[6] = kunci pencarian, data ditemukan : Visual Basic 2005

Kunci Pencarian ? 060

Low ? 0

High ? 7

Posisi = (060 – 025) / (096 – 025) * (7 – 0) + 0 = [3]

Kunci[3] < kunci pencarian, maka teruskan

Low = 3 + 1 = 4

High = 7

Ternyata Kunci[4] adalah 063 yang lebih besar daripada 060.

Berarti tidak ada kunci 060.

Contoh program Interpolation

 

1.     ALGORITMA PENCARIAN MENDALAM (DFS)

            Algoritma pencarian mendalam (DFS) mencari solusi dengan mengunjungi simpul akar, lalu simpul-simpul yang bertetangga dengan simpul akar (setingkat di bawahnya), terus sampai simpul paling dalam pada bagian tersebut. Setelah itu, dicari simpul yang telah dikunjungi pada tingkat terdekat dan terdalam, lalu simpul yang bertetangga dengan simpul ini dikunjungi, demikian seterusnya sampai seluruh simpul telah dikunjungi. Berikut gambar yang mengiilustrasikan urutan simpul yang dikunjungi pada algoritma BFS:

Gambar 2. Ilustrasi urutan kunjungan simpul pada algoritma DFS

                        Dari gambar di atas, dapat dilihat bahwa dengan algoritma DFS, setiap anak          simpul pertama yang bertetangga dengan simpul akar dikunjungi sampai tingkat      terdalamnya lebih dahulu, lalu seluruh simpul pada subpohon tersebut, sebelum simpul        lain yang juga bertetangga dengan simpul akar.

            Cara Kerja Algoritma DFS

                        Dalam algoritma DFS, simpul yang telah dikunjungi disimpan dalam suatu             tumpukan (stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan       dikunjungi sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah        proses runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman maksimal). Untuk memperjelas cara kerja algoritma DFS beserta tumpukan yang digunakannya, berikut langkah-langkah algoritma DFS:

1. Masukkan simpul ujung (akar) ke dalam tumpukan

2. Ambil simpul dari tumpukan teratas, lalu cek apakah simpul merupakan solusi

3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.

4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam tumpukan

5. Jika tumpukan kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan

6. Ulangi pencarian dari langkah kedua

1.      ALGORITMA PENCARIAN MELEBAR (BFS)

            Algoritma pencarian melebar (BFS) mengunjungi setiap simpul dalam graf mulai dari simpul akar, lalu dilanjutkan dengan mengunjungi simpul-simpul yang bertetangga dengan simpul akar tersebut. Setelah itu, untuk setiap simpul yang sudah dikunjungi tersebut, dikunjungi simpul-simpul yang bertetangga dengannya dan belum dikunjungi, demikian seterusnya sampai seluruh simpul berhasil dikunjungi.

Berikut gambar yang mengilustrasikan urutan simpul yang dikunjungi pada algoritma BFS:

 

 

Gambar 1. Ilustrasi urutan kunjungan simpul pada algoritma BFS

Dari gambar di atas, dapat dilihat bahwa dengan algoritma BFS, setiap simpul pada tingkat x dikunjungi lebih dahulu sebelum simpul pada tingkat di bawahnya (x+1).

Cara Kerja Algoritma BFS

            Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yang bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian. Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah algoritma BFS:

1. Masukkan simpul ujung (akar) ke dalam antrian

2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi

3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.

4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian

5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan

6. Ulangi pencarian dari langkah kedua