PENCARIAN (SEARCHING)

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.

B. Pencarian Berurutan
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

Algoritma CARI_VEKTOR_URUT
Langkah 0 Baca vektor yang akan diketahui, misalnya sebagai vector A dengan N elemen.
Langkah 1 Baca data yang akan dicari, misalnya data.
Langkah 2 (Inisialisasi)
Tentukan: ada = False
Langkah 3 (Proses Pencarian).
Untuk I = 1 sampai N kerjakan langkah 4.
Langkah 4 Test apakah : Data = A [I] ?
Jika ya, (berarti data ketemu), tentukan:
Ada=True, posisi=I, dan I=N .
Langkah 5 (Menambah data pada vector, jika diperlukan)
Test apakah Ada=False?
Jika ya, (data tidak ketemu), tentukan:
N=N+1, dan A[I] = data.
Langkah 6 Selesai.

Prosedur dibawah ini menyajikan implementasi algoritma diatas yang diterapkan pada struktur data yang berbentuk Vektor



{***********************************************************
* Prosedur untuk mencari data pada suatu vektor  *
* Dengan metoda PENCARIAN BERURUTAN       *
*************************************************************}
procedure CARI_VEKTOR_URUT (var ada : Boolean;
var N,posisi : integer;
var A     : Larik;
data      : Integer);
var I : integer;

begin
                 {*dianggap data tidak ada*}
                 Ada := False;
                 {*Iterasi Dimulai*}
      for I := 1 to N do
                      if A[I] = data then
                            {*data yang dicari ketemu*}  
                            begin
                     posisi := I;
                                 ada := true;
                                 exit;                {*pencarian selesai*}

                   if not ada then
                       {*data yang dicari tidak ketemu*}
                        *Sisipkan elemen kedalam vector*}
                            Begin
                                Inc(N);
                                A[N] := data
                             End;
               End.

       A[J+1] := T   {* menempatkan elemen *}
    end
end;
 

Prosedure Pencarian menggunakan metode pencarian berurutan pada sebuah vektor

C. 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.
Metode pencarian biner dijelaskan sebagai berikut. 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 data yang 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. Untuk lebih memperjelas penjelasan diatas perhatikan contoh berikut. Dimisalkan kita akan mencari data yang bernilai 20 pada vector berikut ini.


2 8 11 15 18 19 20 22 35 40 45

Vector diatas kita pecahkan menjadi 2 (dua) sub vector sebagai berikut:


2 8 11 15 18 19 20 22 35 40 45
Subvektor 1 Subvektor 2

Dari hasil pemecahan diatas kita lihat bahwa data yang bernilai 20 terdapat pada subvektor 2. dengan demikian pencarian kita laksanakan pada subvektor 2, subvektor 1 tidak perlu dihiraukan lagi. Subvektor 2 kemudian dipecah lagi menjadi:

35 40 45
 
19 20 22
                        subvektor 1       subvektor 2

Sekarang, data yang bernilai 20 terdapat pada subvektor 1, dengan demikian subvektor 1 kita pecah lagi. Proses diteruskan sampai data yang dicari ketemu atau tidak ketemu.
Dari ilustrasi diatas kita susun algoritmanya sebagai berikut:  

Algoritma BINER
Langkah 0 Baca vektor yang akan diketahui, misalnya vector A dengan N buah elemen, dan urutkan secara urut naik.
Langkah 1 Baca elemen yang akan dicari, misalnya data.
Langkah 2 (Inisialisasi)
Tentukan: ada = False,
Atas = N, dan
Bawah = 1.
Langkah 3 Kerjakan langkah 4 dan 5 selama Atas >= Bawah.
Langkah 4 (Menentukan batas subvektor)
Tentukan: Tengah = (Atas + Bawah) div 2
Langkah 5 Test nilai data terhadap A [tengah].
Jika data >  A [tengah], (ada di subvektor 2),
tentukan: Bawah = tengah + 1.
Jika data < A [tengah], (ada di subvektor 1),
Tentukan: Atas = tengah – 1
Jika data = A [tengah], (data ketemu),
Tentukan: Ada = true,
  Posisi = tengah, dan
  Bawah = Atas + 1
Langkah 6 Selesai.

Algoritma pencarian biner yang dijelaskna diatas diimplementasikan dalam prosedur dibawah ini. Dalam hal ini, jika elemen yang akan dicari tidak ditemukan, program tidak akan menambahkanya sebagai elemen baru.



{***********************************************************
* Prosedur untuk mencari data pada suatu vector    *
* Dengan metoda PENCARIAN BINER                    *
***********************************************************}
procedure CARI_BINER (var ada : Boolean;
                                                    var N,posisi : integer;
                                                    var A     : Larik;
                                                    data      : Integer);
var Atas, Bawah, Tengah : integer;\
begin
                 {*dianggap data tidak ada*}
                 Ada := False;
           
                 {*menentukan batas atas dan batas bawah
                 Atas:= N;
                 Bawah:= 1;
 
                {*Iterasi Dimulai*}
     While Atas >=  Bawah do
                          Begin
                             {*elemen yang ada ditengah*}
                              Tengah : = (Atas + Bawah) div 2;

                               If data < A [Tengah] then
                                      {*data kemungkinan ada*
                                       *di subvektor pertama*}
                               Atas := Tengah – 1

                              Else if data > A [Tengah] then
                                      {*data kemungkinan ada*
                                       *di subvektor kedua*}
                               Bawah := Tengah + 1

                               Else
                                       {* data yang dicari sudah ada*}
                                       Begin
                                            Ada := true;
                                            Posisi := Tengah;
                                            Bawah := Atas + 1
                           end;
                  end;
        end.
 

Prosedure Pencarian menggunakan metode pencarian Biner (Binary Search)