Pencarian pada Struktur Data

Pencarian data yang sering juga disebut dengan table look-up atau storage and retrieval information, adalah suatu proses untuk mengumpulkan sejumlah informasi didalam pengingat computer dan kemudian mencari kembali informasi yang diperlukan secepat mungkin. Seperti pada pengurutan data, metode-metode pencarian data juga bisa dikelompokan dengan beberapa cara.

Cara pertama adalah dengan mengelompokan metode pencarian kedalam pencarian internal (internal searching) dan pencarian eksternal (external searching). Dalam pencarian internal, semua rekaman yang diketahui berada dalam pengingat computer. Sedangkan dalam pencarian eksternal, tidak semua rekaman yang diketahui berada dalam pengingat computer, tetapi ada sejumlah rekaman yang tersimpan dalam penyimpanan luar, misalnya pita atau cakram magnetis.

Cara pengelompokan kedua adalah dengan mengelompokannya menjadi Pencarian Statis dan Pencarian Dinamis. Dalam pencarian statis, banyaknya rekaman yang diketahui dianggap tetap. Sedangkan dalam pencarian dinamis banyaknya rekaman yang diketahui bisa berubah-ubah yang disebabkan oleh penambahan atau penghapusan suatu rekaman. 

Pemilihan struktur data yang digunakan untuk menyimpan data yang diketahui akan mempengaruhi efisiensi pencarian itu sendiri. untuk itu, dalam bab ini penulis akan menerapkan beberapa metode untuk dua struktur data yang berbeda, yaitu menggunkan vector dengan deklarasi tipe data array dimensi satu, dan senarai berantai.

Vector yang digunakan mempunyai deklarasi sebagai berikut:

    Type Larik = array [1.. 1000] of integer;

Untuk senarai berantai, deklarasi simpul yang digunakan adalah:

Type List = ^simpul;

        Simpul = record

            Info: integer;

            Kanan: List;

        End;

Pada kedua deklarasi diatas, tipe informasi yang digunakan adalah integer; anda bisa menggunakan tipe data yang lain atau bahkan juga bisa ditambah dengan medan-medan yang lain. Jika dalam suatu program digunakan tipe data yang lain, secara tersendiri akan diberitahukan. 

Pencarian Berurutan

Penjelasan #1:

Metode yang paling sederhana dari sejumlah metode pencarian adalah metode pencarian berurutan (sequential searching), secara garis besar metode ini bisa dijelaskan sebagai berikut; Dari vector yang diketahui, data yang dicari dibandingkan satu per satu sampai data tersebut ditemukan atau tidak ditemukan. Pada saat data yang dicari sudah ketemu, maka proses pencarian langsung dihentikan. 

Tetapi jika data yang dicari belum ketemu, maka pencarian diteruskan sampai seluruh data dibandingkan. Dalam kasus yang paling buruk, untuk vector dengan N elemen harus dilakukan pencarian sebanyak N kali pula. 

Dalam algoritma yang disajikan dibawah ini, jika data yang dicari tidak ditemukan, maka data tersebut akan ditambahkan pada vector yang sudah ada, dan diletakkan sebagai elemen paling akhir 

Penjelasan #2:
Proses yang terjadi pada metode pencarian ini adalah sebagai berikut :

1. Membaca array data.
2. Menentukan array yang dicari.
3. Mulai dari data yang pertama sampai dengan data yang terakhir, data yang dicari dibandingkan dengan masing-masing data di dalam array.
1. Jika data yang dicari tidak ditemukan maka semua data atau elemen array dibandingkan sampai selesai.
2. Jika data yang dicari ditemukan maka perbandingan akan dihentikan.

Pencarian Biner

Cara kedua untuk mencari data pada vector yang elemennya telah diurutkan adalah menggunakan metode pencarian Biner (Binary Search). Jika kita bandingkan, maka metode ini akan jauh lebih cepat dibandingkan dengan metode pencarian berurutan. 

Penjelasan #1:

Setelah vector yang diketahui diurutkan, vector tersebut dibagi menjadi dua sub vector yang mempunyai jumlah elemen yang sama. Kemudian data dibandingkan dengan data terakhir dari subvektor pertama. Jika data yang dicari lebih kecil, pencarian diteruskan pada sub vector pertama dengan terlebih dahulu membagi dua sub vector tersebut.

Tetapi jika data yang dicari lebih besar dari data terakhir pada sub vector pertama, berarti datayang dicari kemungkinan terletak pada sub vector kedua. Dengan demikian pencarian dilakukan pada sub vector kedua. Proses diatas diulang sampai data yang dicari ditemukan atau tidak ditemukan.

Penjelasan #2:

Digunakan untuk pencarian data pada array yang sudah teurut. Proses yang terjadi pada pencarian dengan metoda ini adalah sebagai berikut : 

1. Membaca array data.
2. Apabila array belum terurut, maka diurutkan terlebih dahulu.
3. Menentukan data yang akan dicari.
4. Menentukan elemen tengah dari array.
5. Jika nilai elemen tengah sama dengan data yang dicari maka pencarian selesai.
6. Jika nilai elemen tengah tidak sama dengan data yang dicari maka :
1. Jika nilai elemen tengah lebih besar daripada data yang dicari maka pencarian dilakukan pada setengah array pertama.
2. Jika nilai elemen tengah lebih kecil daripada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.