ALGORITMA SEARCHING

1.      Pengertian Algoritma Pencarian (searching)

Pencarian(searhing) merupakan proses yang fundamental dalam pengolahan data. Proses pensarian adalah menemukan nilai(data) tertentu didalam sekumpulan data yang bertipe sama (baik bertipe dasar maupun bertipe bentukan).

Sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah argumen kunci dan dengan  langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut.  Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful).

1.      Macam-macam Algoritma Pencarian (Searching)

1.1  Pencarian sekuensial (Sequential searching)

·         Pengertian

Pencarian Sekuensial (sequential searching) atau pencarian berurutan sering disebut pencarian linear merupakan metode pencarian yang paling sederhana.  Pencarian beruntun adalah proses membandingkan setiap elemen larik satu per satu secara beruntun, mulai dari elemen pertama sampai elemen yang dicari ditemukan atau seluruh elemen sudah diperiksa. Pencarian beruntun terbadi dua:

1.      Pencarian beruntun pada larik tidak terurut;

2.      Pencarian beruntun pada larik terurut.

·         Algoritma

Pencarian berurutan menggunakan prinsip sebagai berikut :

1.      data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.

2.      Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data.

3.      Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari.

4.       Apabila sama, berarti data telah ditemukan.   Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti data tidak ada.

Kelemahan pada kasus yang paling buruk, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula. Algoritma pencarian berurutan dapat dituliskan sebagai berikut :

(1)           i ← 0

(2)           ketemu ← false

(3)           Selama (tidak ketemu) dan (i <= N) kerjakan baris 4

(4)           Jika (Data[i] = x) maka ketemu ← true, jika tidak i ← i + 1

(5)           Jika (ketemu) maka i adalah indeks dari data yang dicari, jika data tidak ditemukan

·         Contoh

#include <stdio.h>

#include <conio.h>

void main(){

int data[8] = {8,10,6,-2,11,7,1,100};

 int cari;

   int flag=0;

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

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

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

   }

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

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

getch();

return 1;

}

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.

1.1  Pencarian Beruntun dengan Sentinel

·         Pengertian

Jika pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari metode pencarian beruntun yang mangkus. Nilai x yang akan dicari sengaja ditambahkan terlebih dahulu. Data yang ditambahkan setelah elemen terakhir larik ini disebut sentinel.

Perhatikan array data berikut ini:

  0                       1                    2                3                     4                  5              6          indeks

3

12

9

-4

21

6

        ffea                 ffeb          ffec               ffed               ffef                  fffa           fffb       alamat

  

ü Terdapat 6 buah data dalam array (dari indeks 0 s/d 5) dan terdapat 1 indeks array tambahan (indeks ke 6) yang belum berisi data (disebut sentinel)

ü Array pada indeks ke 6 berguna untuk menjaga agar indeks data berada pada indeks 0 s/d 5 saja.  Bila pencarian data sudah mencapai array indeks yang ke-6 maka berarti data TIDAK ADA, sedangkan jika pencarian tidak mencapai indeks ke-6, maka data ADA.

· Algoritma

Procedure SeqSearchWithSentinel(input L: LarikInt, input n: integer, input x: integer, output idx: integer)

DEKLARASI

     I: integer

ALGORITMA

L[n+1]  ← X   {sentinel}

I ← 1

While (L[i] ≠ x) do

                 I ← i+1

Endwhile

If idx = n+1 then

                 idx  ← -1

else

                 idx ← 1

endif

·         Contoh

#include <stdio.h>

#include <conio.h>

void main(){

 int data[7] = {3,12,9,-4,21,6};

 int cari,i;

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

data[6] = cari;

   i=0;

 while(data[i] != cari) i++;

 if(i<6) printf("Data ada!\n"); else printf("Data tidak ada!\n");

getch;

return 1;

}

1.1  Pencarian Biner (binary search)

·         Pengertian

Terdapat metode pencarian pada data terurut yang paling efficient, yaitu metode pencarian bagidua atau pencarian biner (binary search). Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. Data yang disimpan di dalam larik harus sudah terurut.

BST adalah binary tree yang mana data di dalamnya tersusun sedemikian rupa sehingga pada setiap subtree di dalamnya berlaku:

setiap data di subtree kiri < data root subtree < setiap data di subtree kanan.

• Algoritma

class BinaryNode {

      void printInOrder( )‏

      {

              if( left != null )‏

           left.printInOrder( );                               // Left

              System.out.println( element );            // Node

              if( right != null )‏

               right.printInOrder( );                          // Right

   }

}

class BinaryTree {

   public void printInOrder( )‏

   {

              if( root != null )‏

              root.printInOrder( );

   }

}

Prinsip dari pencarian biner dapat dijelaskan sebagai berikut :

1. mula-mula diambil posisi awal 0 dan posisi akhir = N - 1, kemudian dicari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2.
2. Kemudian data yang dicari dibandingkan dengan data tengah.
3. Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.
4. Jika lebih besar, porses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1.
5. Demikian seterusnya sampai data tengah sama dengan yang dicari.

Algoritma pencarian biner dapat dituliskan sebagai berikut : 

1.  L  ← 0
2. R ← N - 1
3. ketemu ← false
4. Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8   
5. m ← (L + R) / 2 83
6.  Jika (Data[m] = x) maka ketemu ← true
7.  Jika (x < Data[m]) maka R ← m – 1 Jika (x > Data[m]) maka L  ← m + 1
8. Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.

•  Contoh

int binary_search(int cari){

int l,r,m;

 l = 0;

   r = n-1;

 int ktm = 0;

 while(l<=r && ktm==0){

                m = (l+r)/2;

               if(data[m] == cari) ktm=1;

               else if (cari < data[m]) r=m-1;

               else l=m+1; {

 if(ktm==1) return 1; else return 0;

}         

}                     

}

1.1  Interpolation Search

·         Pengertian

Teknik ini dilakukan pada data yang sudah terurut  berdasarkan kunci Tertentu. Teknik searching ini dilakukan dengan perkiraan letak data.

Contoh ilustrasi: jika kita hendak mencari suatu nama di dalam buku telepon, misal yang berawalan dengan huruf T, maka kita tidak akan mencarinya dari awal buku, tapi kita langsung membukanya pada  2/3 atau ¾ dari tebal buku. Jadi kita mencari data secara relatif terhadap jumlah data. Rumus posisi relatif kunci pencarian dihitung dengan rumus:

Posisi =       kunci – data[low]       x (hight – low) + low

              Data[hight] – data[low]

Misal terdapat data sebagai berikut:

Kode	Judul Buku	Pengarang
025	The C++ Programming	James Wood
034	Mastering Delphi 6	Marcopolo
041	Professional C#	Simon Webe
056	Pure JavaScript v2	Michael Bolton
063	Advanced JSP & Servlet	David Dunn
072	Calculus Make it Easy	Gunner Christian
088	Visual Basic 2005 Express	Antonie
096	Artificial Life : Volume 1 Gloria	Virginia

Kunci Pencarian ? 088

Low ? 0 

High ? 7

Posisi = (088 - 025) / (096 - 025) * (7 - 0) + 0 = [6]

Kunci[6] = kunci pencarian, data ditemukan : Visual Basic 2005

Kunci Pencarian ? 060

Low ? 0

High ? 7

Posisi = (060 – 025) / (096 – 025) * (7 – 0) + 0 = [3]

Kunci[3] < kunci pencarian, maka teruskan

Low = 3 + 1 = 4

High = 7

Ternyata Kunci[4] adalah 063 yang lebih besar daripada 060.

Berarti tidak ada kunci 060.

·         Contoh Program

#include <stdio.h>

#include <stdlib.h>

#define MAX 5

int interpolationsearch(int a[],int low,int high,int x){

      int mid;

      while(low<=high){                            

                  mid=low+(high-low)*((x-a[low])/(a[high]-a[low]));

                  if(x==a[mid])

                              return mid+1;

                  if(x<a[mid])

                              high=mid-1;

                  else

                              low=mid+1;

      }

       return -1;

}

int main(){

      int arr[MAX];

      int i,n;

      int val,pos;

       

     printf("\nEnter total elements (n < %d) : ",MAX);

      scanf("%d",&n);

       printf("Enter %d Elements : ",n);

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

                  scanf("%d",&arr[i]);

                  printf("\nLIST : ");          

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

                   printf("%d\t",arr[i]);

                  printf("\nSearch For : ");

                  scanf("%d",&val);

                  pos=interpolationsearch(&arr[0],0,n,val);

                  if(pos==-1)

                              printf("\nElement %d not found\n",val);

                              else

                                          printf("\nElement %d found at position %d\n",val,pos);

           return 0;

}