Pencarian (Searching)

a.             Pengertian

Pencarian (searching) merupakan proses yang sering digunakan  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 keynya adalah A.

Algoritma bisa mengembalikan nilai record, atau pointer ke record. Reord sendiri adalah tipe data yang terdiri atas kumpulan variabel disebut field. Sequential search (penelusuran sequensial) yaitu proses mengunjungi melalui suatu pohon dengan cara setiap simpul di kunjungi hanya satu kali yang disebut dengan tree transversal / kunjungan pohon.

Data dapat disimpan secara temporer dalam memori utama atau disimpan 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 aesip (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 keberadaan 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 di tambahkan, tetapi jika belum ada, maka tambahkan. Algoritma pencarian yang akan dibicarakan adalah algoritma pencarian yang paling sederhana yaitu pencarian beruntun atau sequential search.

b.             Penjelasan

Sequential search 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). 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).

Prinsip kerja dari Sequential Searching ini adalah semua data di cek oleh variabel cari. Sequential search dibedakan menjadi dua macam yaitu Pencarian beruntun pada larik tidak terurut dan pencarian beruntun pada larik terurut.

1.        Pencarian beruntun pada larik tidak terurut (acak)

Pencarian dilakukan dengan memeriksa setiap elemen larik mulai dari elemen pertama sampai elemen yang dicari ditemukan atau sampai seluruh elemen sudah diperiksa.

Diketahui sebuah tabel TabInt [1..N] yang telah berisi nilai dengan tipe integer. Jika pada tabel tersebut akan dicari apakah harga/nilai X ada dalam TabInt tersebut ? Maka pencarian yang akan dilakukan adalah membandingkan setiap nilai pada tabel tersebut dengan nilai X yang dicari. Proses tersebut dilakukan secara berurutan mulai dari elemen pertama sampai ketemu, atau sampai elemen terakhir. Apabila niali X ditemukan maka harga/nilai indeks I di mana X diketemukan pertama kalinya akan bernilai tidak sama dengan nol (I ¹ 0). I diberi harga 0 jika pencarian tidak ketemu. Pencarian segera dihentikan begitu harga pertama diketemukan.

Contoh :          13        87        14        21        75        53

• Misal nilai yang dicari adalah X = 21, maka elemen yang diperiksa adalah 13, 87, 14, 21. (ditemukan)

          Jadi indeks larik yang dikembalikan : I = 4

• Misal nilai yang dicari adalah X = 15, maka elemen yang diperiksa adalah 13, 87, 14, 21, 75, 53. (tidak ditemukan)

          Jadi indeks larik yang dikembalikan : I = 0

DETAIL PROGRAM

#include <stdio.h>

#include <conio.h>

void main(){

                        clrscr();

                        int data[21] = {13, 87, 14, 21, 75, 53};

                        int cari;

                        int flag=0;

                        printf("masukkan data yang ingin dicari = "); scanf("%d",&cari);

                        for(int i=0;i<21;i++){

                                    if(data[i] == cari) flag=4;}

                        if(flag==1) printf("Data ada!\n");

         else printf("Data tidak ada!\n");}

2.      Pencarian beruntun pada larik terurut

Pencarian dilakukan dengan memeriksa setiap elemen larik yang berurutan mulai dari elemen pertama sampai elemen yang dicari ditemukan atau sampai seluruh elemen sudah diperiksa.

Diketahui sebuah tabel bilangan integer TabInt[1..N], yang telah diisi dan isinya terurut membesar ( untuk setiap i anggota dari [1..N-1], Ti < T i+1). Jika pada tabel tersebut akan dicari apakah harga/nilai X ada dalam TabInt tersebut ? Maka pencarian yang akan dilakukan adalah membandingkan setiap nilai pada tabel tersebut dengan nilai X yang dicari. Proses tersebut dilakukan secara berurutan mulai dari elemen pertama sampai ketemu, atau sampai kepada elemen terakhir atau sampai dengan harga X yang beinilai lebih besar dari nilai elemen suatu posisi yang sedang diakses pada tabel. Apabila niali X ditemukan maka harga/nilai indeks I di mana X diketemukan pertama kalinya akan bernilai tidak sama dengan nol (I ¹ 0). I diberi harga 0 jika pencarian tidak ketemu.

Contoh : 55     56        78        80        100      156      199

• Misal nilai yang dicari adalah X = 100, maka elemen yang diperiksa adalah 55, 56, 78, 80, 100. (ditemukan)

          Jadi indeks larik yang dikembalikan : I = 5

• Misal nilai yang dicari adalah X = 170, maka elemen yang diperiksa adalah 55, 56, 78, 80, 100, 156, 199. (tidak ditemukan)

          Jadi indeks larik yang dikembalikan : I = 0

DETAIL PROGRAM

#include <stdio.h>

#include <conio.h>

void main(){

                        clrscr();

                        int data[100] = {55,56,78,80,100,156,199};

                        int cari;

                        int flag=0;

                        printf("masukkan data yang ingin dicari = "); scanf("%d",&cari);

                        for(int i=0;i<100;i++){

                                    if(data[i] == cari) flag=1;}

                        if(flag==1) printf("Data ada!\n");

         else printf("Data tidak ada!\n");}

Ø  Dari program diatas, terlihat bahwa dilakukan perulangan untuk mengakses semua elemen array data satu persatu berdasarkan indeksnya.

Ø  Program menggunakan sebuah variabel flag yang berguna untuk menadai ada atau tidaknya data yang dicari dalam array data.  Hanya bernilai 0 atau 1.

Ø  Flag pertama kali diinisialiasasi dengan nilai 0.

Ø  Jika ditemukan, maka flag akan diset menjadi 1, jika tidak ada maka flag akan tetap bernilai 0.

Ø  Semua elemen array data akan dibandingkan satu persatu dengan data yang dicari dan diinputkan oleh user.

c.      Contoh Program

Program pencarian ;

Uses crt;

Label 1;

Var

L:array [1..100] of integer;

Bil,I,n:integer;

ul:char;

procedure tampil;

begin

write (‘masukan banyak data:’); readln (n);

for i:=1 to n do

begin

write (‘data [‘,I,’] :’);readln (L [i]);

end;

end;

procedure seq_search;

begin

write (‘angka yang akan di cari:’);readln (bil);

i : =1;

while (I <n) and (L[i] <> bil) do

begin

i:=i+1;

end;

if (L[i]=bil)then

writeln (‘ditemukan pada elemen larik ke’,i)

else

writeln (‘tidak ditemukan’);

end;

begin

1 :

Clrscr;

Writeln (‘----------------------------------------------------------’);

Writeln (‘------ PROGRAM PENCARIAN ANGKA ----‘);

Writeln (‘----------------------------------------------------------‘);

Tampil;

Seq_search;

Writeln ;

Delay (3000);

Write (‘apakah anda ingin mengulangi [Y/T] ? : ‘);readln (ul);

If (ul =’Y’) or (ul =’y’) then

Goto 1 ;

Readkey;

End.