Pencarian (searching) merupakan proses
fundamental dalam pengelolaan data. Proses pencarian adalah menemukan nilai
(data) tertentu di dalam sekumpulan data yang bertipe sama (baik bertipe dasar
atau bertipe bentukan). Search algoritma adalah algoritma yang menerima
argument a dan mencoba untuk mencari
record yang mana key-nya adalah Algoritma bisa mengembalikan nilai record, atau
pointer ke record.
Record sendiri adalah tipe data yang terdiri atas kumpulan
variabel yang dapat berbeda tipenya. Setiap variabel disebut field. Sequensial
Search (penelusuran sequensial) yaitu proses mengunjungi melalui suatu pohon
dengan cara setiap simpul di kunjungi hanya satu kali yang disebut tree
transversal / kunjungan pohon. Sedangkan Binary Search adalah penelusuran pohon
biner dimana data yang dimasukkan atau yang sudah ada diurutkan terlebih
dahulu.
Data dapat di simpan secara temporer dalam memori utama atau di simpan secara permanen di dalam memori sekunder (tape atau disk). Di dalam memori utama, struktur penyimpanan data yang umum adalah berupa larik atau tabel (array), sedangkan di dalam memori sekunder berupa arsip (file). Aktivitas yang berkaitan dengan pengolahan data ini sering di dahului dengan proses pencarian. Sebagai contoh, untuk mengubah (update) data tertentu, langkah pertama yang harus dilakukan adalah mencari keberadaaan data tersebut di dalam kumpulannya. Aktivitas yang awal sama juga dilakukan pada proses penambahan (insert) data yang baru. Proses penambahan data dimulai dengan mencari apakah data yang ditambahkan sudah terdapat di dalam kumpulan. Jika sudah dan mengasumsikan tidak boleh ada duplikasi data maka data tersebut tidak perlu ditambahkan, tetapi jika belum ada, maka tambahkan.
Algoritma pencarian yang akan dibicarakan dimulai dengan algoritma pencarian yang paling sederhana yaitu pencarian beruntun atau Sequential Search sampai pada algoritma pencarian yang lebih maju yaitu pencarian bagi dua (Binary Search).
Data dapat di simpan secara temporer dalam memori utama atau di simpan secara permanen di dalam memori sekunder (tape atau disk). Di dalam memori utama, struktur penyimpanan data yang umum adalah berupa larik atau tabel (array), sedangkan di dalam memori sekunder berupa arsip (file). Aktivitas yang berkaitan dengan pengolahan data ini sering di dahului dengan proses pencarian. Sebagai contoh, untuk mengubah (update) data tertentu, langkah pertama yang harus dilakukan adalah mencari keberadaaan data tersebut di dalam kumpulannya. Aktivitas yang awal sama juga dilakukan pada proses penambahan (insert) data yang baru. Proses penambahan data dimulai dengan mencari apakah data yang ditambahkan sudah terdapat di dalam kumpulan. Jika sudah dan mengasumsikan tidak boleh ada duplikasi data maka data tersebut tidak perlu ditambahkan, tetapi jika belum ada, maka tambahkan.
Algoritma pencarian yang akan dibicarakan dimulai dengan algoritma pencarian yang paling sederhana yaitu pencarian beruntun atau Sequential Search sampai pada algoritma pencarian yang lebih maju yaitu pencarian bagi dua (Binary Search).
Jenis-jenis
Searching
A.
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).
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.
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.
B. 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.
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.
C. 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:
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.
Contoh
Pemrograman Searching dalam Algoritma
A.
Contoh
program dalam bahasa pemrograman PASCAL
program search_aditya;
uses crt;
const
nmin = 1;
nmax = 100;
type
arrint = array [nmin..nmax]
of integer;
var
x
: integer;
tabint : arrint;
n,i :
integer;
indeks : integer;
function seqsearch1(xx :
integer): integer;
var i : integer;
begin
i := 1;
while ((i xx)) do
i:=i+1;
if tabint[i] = xx then
seqsearch1:=i
else
seqsearch1:=0;
end;
begin
clrscr;
write('input banyaknya
index array = '); readln(n);
for i:=1 to n do
begin
write('Tabint[',i,'] = ');
readln(tabint[i]);
end;
write('Nilai yang dicari =
'); readln(x);
indeks:=seqsearch1(x);
if indeks <> 0 then
write(x,' ditemukan pada
indeks ke-',indeks)
else
write(x,' tidak
ditemukan');
writeln;
readln;
end.
Posting Komentar