Algoritma Searching

Pengertian Algoritma Searching

Searching merupakan proses dasar dalam pengolahan data. Yaitu untuk menemukan nilai tertentu dalam sekumpulan data yang bertipe sama. Algoritma searching dijelaskan secara luas sebagai algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut. Algoritma searching menerima sebuah argument kunci dan dengan langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut. Setelah melakukan proses pencarian, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan atau tidak ditemukan.
Macam-macam Algoritma Searching
1. Pencarian Beruntun (Sequential Search)
Konsep
a)      Membandingkan setiap elemen larik satu per satu secara urut (beruntun), mulai dari elemen pertama sampai dengan elemen yang terakhir sampai data ditemukan atau tidak ditemukan.
b)      Proses pencarian akan dihentikan jika data yang dicari sudah ditemukan.
c)      Merupakan metode yang paling sederhana
d)     Kelemahan pada kasus ini adalah, untuk N elemen data harus dilakukan pencarian sebanyak N kali pula.
Algoritma
Algoritma pencarian beruntun 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 di atas, terlihat bahwa dilakukan perulangan untuk mengakses semua elemen array data satu per satu berdasarkan indeksnya.
a)      Program menggunakan sebuah variable flag yang berguna untuk menandai ada atau tidaknya data yang dicari dalam array data. Hanya bernilai 1 atau 0.
b)      Flag pertama kali diinisialisasi dengan nilai 0.
c)      Jika ditemukan, maka flag akan diset menjadi 1, jika tidak ada maka flag akan tetap bernilai 0.
d)     Semua elemen array data akan dibandingkan satu per satu dengan data yang dicari dan diinputkan oleh user.
2. Pencarian Beruntun dengan sentinel
Konsep
a)      Pencarian bertujuan untuk menambahkan elemen baru setelah elemen terakhir larik, maka terdapat sebuah varian dari metode pencarian berurutan. NIlai x yang akan dicari sengaja ditambahkan terlebih dahulu. Data yang ditambahkan setelah elemen larik ini disebut dengan sentinel.
b)      Perhatikan array berikut ini:

0	1	2	3	4	5	6	indeks
3	12	9	-4	21	6
ffea	ffeb	ffec	ffed	ffef	fffa	fffb	alamat

(1)   Terdapat enam buah data dalam array (dari indeks 0 s.d. lima dan terdapat 1 indeks array tambahan (indeks ke 6) yang belum berisi data (disebut sentinel)
(2)   Array pada indeks ke-6 berguna untuk menjaga agar indeks data berada pada indeks 0 s.d. 5 saja. Nila 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;
}
3. Pencarian Bagi Dua (Binary Search)
Konsep
(a)    Merupakan metode pencarian pada data terurut yang paling efisien.
(b)   Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat.
(c)    Prinsip pencarian dengan membagi data atas dua bagian mengilhami metode ini. data yang disimpan didalam larik harus sudah terurut.
Algoritma
Algoritma pencarian biner dapat dituliskan sebagai berikut:
(a)    L ← 0
(b)   R ← N – 1
(c)    Ketemu ← false
(d)   Selama (L <= R) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8
(e)    m ← (L + R) / 283
(f)    jika (Data[m]) maka ketemu ← true
(g)   jika (x < Data[m]) maka R ← m – 1
(h)   jika (x > Data[m]) maka L ← m + 1
(i)     jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak maka 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;
   }
  }
}


Sumber Referensi :

http://hadiahdi.wordpress.com/2012/05/11/algoritma-searching/