Struktur Data Searching

Pengertian Searching

Searching adalah pencarian data dengan cara menelusuri data-data tersebut. Tempat pencarian data dapat berupa array dalam memori, bisa juga pada file pada external storage. Jika diketahui ada sebuah array / barisan data bernama A yang menampung 10 data yang bertipe integer sebagai berikut  :

            A={1,2,3,4,8,5,7,9,6,0} 
kita diberi tugas untuk mencari beberapa data misal :
Jika data yang akan dicari dalam array A adalah 6, maka dengan cepat dapat kita ketahui bahwa data 6 ada dalam array A pada index ke-9 (index pada array dimulai dari 0). Sedangkan jika data yang akan dicari dalam array A adalah 12, maka dapat disimpulkan bahwa array A tidak memiliki data 12 tersebut. Permasalahannya adalah bagaimana mengimplementasikannya kedalam program?
Pada umumnya dikenal dua metode searching antara lain :

1. Sequensial search 
Disebut juga sebagai metode pencarian urut adalah metode pencarian yang paling mudah. 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.

Ada 2 Kemungkinan dalam Sequensial Search 

·         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). 

2. Binary Search 

Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu. 

Prinsip dari Binary Search

·         Mula-mula diambil posisi awal 0 dan posisi akhir = N-1, kemudian dicari posisi data tengah dengan rumus (posisi awal + posisi akhir) / 2. Kemudian data yang dicari dibandingkan dengan data tengah.

·         Jika lebih kecil, proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah –1.

·         Jika lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1.

·         Jika data sama, berarti data ditemukan

Contoh 

Contoh Program Searching (Sequensial)

#include<stdio.h>
#include<iostream.h>
#include<conio.h>
void main()
{
 //deklarasi variabel
 int A[10],index[10], i,j,k,n;

 //proses penginputan data
   cout<<"Masukkan jumlah data [Max 10] : ";
   cin>>n;

 for(i=0;i<n;i++)
 {
    cout<<"Masukkan Data ke - "<<(i+1)<<" = ";
      cin>>A[i];
 }

 //memasukkan data yang akan dicari ke dalam K
   cout<<"Masukkan data yang anda akan cari : ";
   cin>>k;

 //proses pencarian data
 j=0;
 for (i=0;i<n;i++)
 {
  if(A[i]==k)
  {
   index[j]=i;
   j++;
  }
   }

 //jika data ditemukan dalam array
 if (j>0)
 {
  cout<<"Data" <<k<< "yang dicari ada" <<j<< "buah"<<endl;
      cout<<"Data tersebut terdapat dalam index ke : ";
    for(i=0;i<j;i++)
  {
         cout<<index[i]<<" ";
  }
      cout<<endl;
 }

 //jika tidak ditemukan
 else
 {
      cout<<"Data tidak ditemukan dalam array"<<endl;;
 }
  getch();
}

Screenshot Program Searching (Squensial)

Contoh Program Searching (Binary)

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
void main()
{
 //deklarasi variabel
 int A[10],n, i,j,k,tkr,right,left,middle,tm;

 //proses penginputan data
   cout<<"Masukkan jumlah data = ";
   cin>>n;
 for(i=0;i<n;i++)
 {
    cout<<"Masukkkan data ke - "<<(i+1)<<" = ";
      cin>>A[i];
 }
   cout<<"Masukkan data yang akan anda cari :";
   cin>>k;

 //proses pengurutan data
 for(i=0;i<n;i++)
 {
  for(j=i+1;j<n;j++)
  {
   if (A[i]>A[j])
   {
    tkr=A[i];
    A[i]=A[j];
    A[j]=tkr;
         }
      }
   }

 //proses pencarian data
 tm=0;
 right=n;
 left=0;
 while(right>=left)
 {
  middle=(right+left)/2;
  if(A[middle]==k)
  {
   tm++;
  }
  if(A[middle]<k)
  {
   left=middle+1;
  }
  else
  {
   right=middle-1;
  }
   }
 if (tm>0)
   {
    cout<<"Data " << k << " yang dicari ada dalam array"<<endl;
   }
 //jika tidak ditemukan
 else
 {
    cout<<"Data tidak ditemukan dalam array"<<endl;
   }
   getch();
}

Screenshot Program Searching (Binary)