Searching (Sequential Search dan Binarry Search)

Pengantar Pencarian Data

Pencarian (searching) merupakan tindakan untuk mendapatkan suatu data dalam kumpulan data. Dalam kehidupan sehari hari, seringkali kita berurusan dengan pencarian; misalnya untuk menemukan nomor telepon seseorang pada buku telepon atau mencari suatu istilah dalam kamus. Pada aplikasi komputer, pencarian kerap dilakukan; misalnya untuk mendapatkan data dari seorang mahasiswa, mendapatkan nomor telepon berdasarkan suatu alamat atau nama perusahaan.

Untuk keperluan mencari data, terdapat beberapa algoritma pencarian. Yang dimadsud dengan algoritma pencarian adalah "algoritma yang menerima sebuah argumen a dan mencoba untuk menemukan sebuah rekaman yang memiliki kunci a". Sebagai contoh, dikehendaki untuk mendapatkan mahasiswa dengan nomor 140010289. Hasilnya adalah rekaman yang berisi data mahasiswa tersebut; yang barang kali berisi nama, alamat, tanggal lahir, dan nama program studi. Dalam implementasi, algoritma bisa jadi memberikan nilai balik berupa sebuah rekaman yang diperoleh, tetapi bisa hanya memberikan pointer yang menunuk ke sebuah rekaman.

Pencarian dapat dilakukan terhadap data yang secara keselurahan berada dalam memori komputer ataupun terhadap data yang berada dalam penyimpanan eksternal (harddisk). Pencarian yang dilakukan terhadap data yang berada dalam memori komputer dikenal dengan sebutan pencarian internal, sedangkan pencarian yang dilakukan pada media penyimpanan eksternal disebut pencarian eksternal. Pencarian internalah yang akan kita bahas.

Sequential Search (Pencarian Sekuensial)

Pencarian sekuensial (atau disebut juga pencarian linear) merupakan model pencarian yang paling sederhana yang dilakukan terhadap suatu kumpulan data.

Secara konsep, penjelasannya adalah seperti berikut: terdapat L yang merupakan larik yang berisi n buah data (L[0],L[1],...,L[n-1]) dan k adalah data yang hendak dicari. Pencarian dilakukan untuk menemukan

L[i] = k

dengan i adalah bilangan indeks terkecil  yang memenuhi kondisi 0<=k<=n-1. Tentu saja ada kemungkinan bahwa data yang dicari tidak ditentukan. Contoh:

L <- [10,9,4,6,4,3,2,5]

Dimanakah posisi 4 yang pertama? Dalam hal ini k adalah 4 dan k ditemukan pada posisi dengan indeks berupa 2.

Contoh :

1.Implementasi pencarian sekuensial yang digambarkan di atas dalam bentuk algoritma dan program

Algoritma:

Subrutin berikut merupakan implementasi algoritma pencarian secara sekuensial. Dalam hal ini subrutin menghasilkan nilai balik berupa:

• -1 jika data yang dicari tidak ditemukan, dan
• bilangan antara 0 sampai dengan n-1 (dengan n adalah jumlah elemen larik) jika data yang dicari ditemukan.

SUBRUTIN cari(L,n,k)

       JIKA n<= 0 MAKA

              posisi <- -1

       SEBALIKNYA

              ketemu <- SALAH

              i <- 0

              ULANG SELAMA (i<n-1) DAN (TIDAK ketemu)

                   JIKA k = L[i] MAKA

                         posisi <- i

                         ketemu <- BENAR

                   SEBALIKNYA

                         i <- i+1

                   AKHIR-JIKA

             AKHIR-ULANG

             JIKA TIDAK ketemu  MAKA

                   posisi <- -1

             AKHIR-JIKA

      AKHIR-JIKA

    

      NILAI-BALIK posisi

AKHIR-SUBRUTIN

Program:

#include <iostream.h>

#include <conio.h>

int cari(int data[], int n, int k)

{

   int posisi, i, ketemu;

   if (n <= 0)

      posisi = -1;

   else

   {

      ketemu = 0;

      i = 1;

      while ((i < n-1) && ! ketemu)

         if (data[i] == k)

         {

            posisi = i;

            ketemu = 1;

         }

         else

            i++;

      if (!ketemu)

         posisi = -1;

   }

   return posisi;

}

int main()

{

   int data[8] = { 6, 7, 8, 5, 7, 8, 1, 9};

   int dicari = 5;

   cout << "Posisi " << dicari << " dalam larik data: "

        << cari(data, 8, dicari) << "\n";

   getch ();

   return 0;

}

Hasil eksekusi program:

2. Tulislah algoritma untuk menghitung jumlah suatu bilangan dalam larik L yang berisi n buah elemen.

Algoritma:

SUBRUTIN hitung(L,n,k)

       jumlah <- 0

       UNTUK i <- 0 S/D n-1

           JIKA k = L[i] MAKA

                 jumlah <- jumlah+1

           AKHIR-JIKA

      AKHIR-UNTUK

   NILAI-BALIK jumlah

AKHIR-SUBRUTIN

Program:

#include <iostream.h>

#include <conio.h>

int hitung(int data[], int n, int k)

{

   int jumlah, i, ketemu;

   jumlah = 0;

   for (i = 1; i < n; i++)

      if (data[i] == k)

         jumlah++;

   return jumlah;

}

int main()

{

   int data[8] = { 6, 7, 8, 5, 7, 8, 1, 9};

   int dicari = 8;

   cout << "Banyak bilangan " << dicari

        << " dalam larik data: "

        << hitung(data, 8, dicari) << "\n";

   getch ();

   return 0;

}

Hasil eksekusi program:

Binary Search (Pencarian Terhadap Data Urut)

Apabila kumpulan data sudah terurut , pencarian data dengan menggunakan pencarian sekuensial akan memakan waktu yang lama jika jumlah data dalam kumpulan data tersebut sangat banyak. Untuk mengatasi hal itu terdapat algoritma yang dirancang agar pencarian data dapat dilakukan secara efisien. Metode yang digunakan dikenal dengan nama pencarian biner (binary search). Pencarian biner hanya bisa dilakukan jika data sudah terurut.

Pencarian biner dilakukan dengan membagi larik menjadi dua bagian dengan jumlah yang sama atau berbeda 1 jika jumlah data semula ganjil. Data yang dicari kemudian dibandingkan dengan data terakhir pada bagian pertama. Dalam hal ini ada tiga kemungkinan yang terjadi:

• data yang dicari sama dengan elemen terakhir pada bagian petama dalam larik. Jika kondisi ini terpenuhi , data yang dicari berarti ditemukan.
• data yang dicari bernilai kurang dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian pertama.
• data yang dicari bernilai lebih dari nilai elemen terakhir pada bagian pertama dalam larik. Pada keadaan ini, pencarian diteruskan pada bagian kedua.

Contoh program:

#include <iostream.h>

#include <conio.h>

int caribin(int data[], int n, int k)

{

   int ada, atas, bawah, tengah, posisi;

   ada = 0;

   bawah = 0;

   atas = n-1;

   while (atas >= bawah)

   {

      tengah = (atas + bawah) / 2;

      if (k > data[tengah])

         bawah = tengah + 1;

      else

         if (k < data[tengah])

            atas = tengah - 1;

         else

         {

            ada = 1;           /* Ketemu   */

            posisi = tengah;

            bawah = atas + 1;  /* Mengakhiri pengulangan */

         }

   }

   if (!ada)

      posisi = -1;

   return posisi;

}

int main()

{

   int data[] = { 1, 2, 4, 4, 5, 7, 8, 10, 13, 14, 15};

   int dicari = 13;

   cout << "Posisi " << dicari << " dalam larik data: "

        << caribin(data, 11, dicari) << "\n";

   getch ();

   return 0;

}

Hasil eksekusi program:

Data yang belum terurut harus diurutkan terlebih dahulu dengan menggunakan tehnik sorting.