SEARCHING

SEARCHING (Sequential Search dan Binarry Search)

Searching adalah metode pencarian informasi dalam suatu aplikasi, dengan suatu kunci( key ). Pencarian diperlukan untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui. Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut table.

Pada metode searching (pencarian) ada 2 teknik yang digunakan yaitu :

a. Pencarian sekuensial (sequential search)

b. Pencarian biner (Binary search).

a. Sequential Search

Pencarian sekuensial (sequential search) atau sering disebut pencarian linier menggunakan prinsip sebagai berikut : data yang ada di bandingkan satu persatu secara berurutan dengan yang dicari. Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap perulangan , di bandingkan data ke-i dengan yang dicari. Apabila sama , berarti data telah ditemukan . Sebaliknya apabila sampai akhir pengulangan , tidak ada yang sama berarti data tidak ada.

Pencarian Sekuensial memiliki beberapa kelebihan dan kekurangan yaitu :

1.       Kelebihannya :

•  Relatif lebih cepat dan efisien untuk data yang terbatas
• Algoritma sederhana

2.       Kekuranganya :

• Kurang cepat untuk data dalam jumlah besa
• Beban komputasi cenderung lebih besar

CONTOH PROGRAM PADA C++

#include <stdio.h>
#include <iostream.h>
#include <conio.h>

main()
{
int n,i,posisi,x,temu;
int a[5];
printf("Pencarian data dengan sequential search \n\n");
printf("Banyak data : ");
scanf("%d",&n);

for(i=0;i<n;i++)
{
printf("Masukan bilangan : ");
scanf("%d",&a[i]);
}
printf("Data yang akan dicari : ");
scanf("%d",&x);
temu=0;
i=0;
while((temu == 0)&&(i<n))
{
if(a[i]==x)
{
temu=1;
posisi=i;
}
else
i=i+1;
}
if(temu==1)
printf("%d Ditemukan pada posisi %d\n",x,posisi+1);
else
  printf("%d Tidak ditemukan \n",x);
getch();
}


HASIL
 

b. Binarry Search

Binary search adalah sebuah algoritma pencarian dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian untuk menemukan nilai tertentu dalam sebuah larik (array) linear. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama. Pencarian Biner (Binary Search) dilakukan untuk :

a)      Memperkecil jumlah operasi pembandingan yang harus dilakukan antara data yang dicari dengan data yang ada di dalam tabel, khususnya untuk jumlah data yang sangat besar ukurannya.

b)      Beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah.

c)      Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data ditemukan atau sampai ruang pencarian tidak dapat dibagi lagi (berarti ada kemungkinan data tidak ditemukan).

d)     Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut.

Langkah dalam pencarian biner adalah :

1.      Mula-mula diambil dari posisi awal=1 dan posisi akhir = n

2.      Kemudian kita cari posisi data tengah dengan rumus posisi tengah = (posisi awal + posisi akhir ) div 2

3.      Kemudian data yang di cari dibandingkan dengan data tengah

a.       Jika sama, data ditemukan, Proses selesai

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

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

4.      Ulangi langkah kedua hingga data ditemukan , atau tidak ditemukan.

5.       Pencarian biner ini akan berakhir jika data ditemukan posisi awal lebih besar dari pada posisi akhir. Jika posisi awal sudah lebih besar dari posisis akhir berarti data tidak diketemukan.

 Pencarian Biner :

a.       Kelebihannya :

o   Untuk data dalam jumlah besar, waktu searching lebih cepat

o   Beban komputasi lebih kecil

b.      Kekuranganya :

o   Data harus sudah di-sorting lebih dulu ( dalam keadaan terurut )

Contoh Program Binary Search pada Bahasa C++ :

#include <iostream.h>
#include <conio.h>

int data[10]={1,3,4,7,12,25,40,65,78,90};
int binary_search(int cari)
{
int a,b,c;
int n=10;
a=0;
b=n-1;
int ketemu=0;
while (a<=b && ketemu==0)
{
c=(a+b)/2;
if (data[c]==cari)
ketemu=1;
else
if(cari<data[c])
b=c-1;
else a=c+1;
}
if(ketemu==1) return 1; else return 0;
}

void main()
{
clrscr();
int cari, hasil;
cout<<"masukan data yang ingin di cari= ";
cin>>cari;
hasil = binary_search(cari);
if(hasil==1)
{
cout<<"data ada!"<<endl;
}
else
if(hasil==0)
cout<<"data tidak ada!"<<endl;
getch();
}

referensi :   materi dari ppt. teori struktur data/ STIKOM-Bali
                 Coding dari dosen praktikum struktur data/ STIKOM-Bali/ dengan sedikit perubahan