Macam-macam Algoritma Pencarian (Searching)

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
Algoritma Sequential Searching dalam bahasa C

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

void main()
{
    int i;
    int cari,ketemu;
  int A[100]  ;

   cout<<"PROGRAM SEARCHING\n";
   cout<<"masukkan 7 buah data : \n\n";
   for (i=1;i<=7;i++)
   {
   cout<<"masukkan data ke-"<<i<<endl;
   cin>>A[i] ;
   }
   cout<<endl;
    cout<<"Input bilangan yang dicari : ";
    cin>>cari;

    ketemu=0;
    for(i=0;i<=7;i++)
    {
        if (A[i]==cari)
        {
            ketemu=1;
            cout<<"Data ditemukan pada indeks ke-"<<i;
        }
    }

    if (ketemu==0){
       cout<<"Data tidak ditemukan";
    }

 getch();
}

Contoh program nya dalam bahasa C :

#include <stdio.h>
#include <conio.h>
void main(){
int data[10] = {8,10,6,-2,11,7,1,100,11,3};
 int cari;
   int flag=0;
  printf("data = 8,10,6,-2,11,7,1,100,11,3")
  printf("masukkan data yang ingin dicari = ");scanf("%d",&cari);
   for(int i=0;i<10;i++){
                if(data[i] == cari) flag=1;
   }
   if(flag==1) printf("Data ada!\n"); 
else printf("Data tidak ada!\n");
getch();
return 1;
}

hasil nya adalah :

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.

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.

· 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 dalam bahasa c :

#include <stdio.h>
#include <conio.h>
void main(){
 int data[11] = {3,12,9,-4,21,6,1,2,8,7,4};
 int cari,i;

printf("3,12,9,-4,21,6,1,2,8,7,4");
printf("masukkan data yang ingin dicari = ");scanf("%d",&cari);
data[11] = cari;
   i=0;
 while(data[i] != cari) i++;
 if(i<11) printf("Data ada!\n"); else printf("Data tidak ada!\n");
getch;
}

hasil nya adalah :

Contoh 1 program dalam bahasa c ++ :

#include <iostream.h>
#include <conio.h>
void main()
{
    int i;
    int cari,ketemu;
  int A[100]  ;
   cout<<"PROGRAM SEARCHING\n";
   cout<<"masukkan 7 buah data : \n\n";
   for (i=1;i<=7;i++)
   {
   cout<<"masukkan data ke-"<<i<<endl;
   cin>>A[i] ;
   }
   cout<<endl;
    cout<<"Input bilangan yang dicari : ";
    cin>>cari;
    ketemu=0;
    for(i=0;i<=7;i++)
    {
        if (A[i]==cari)
        {
            ketemu=1;
            cout<<"Data ditemukan pada indeks ke-"<<i;
        }
    }
    if (ketemu==0){
       cout<<"Data tidak ditemukan";
    }
 getch();
}

hasil nya adalah :

Contoh 2 program dalam bahasa c ++ :

#include <iostream.h>
#include <conio.h>
void main()
{
clrscr();
int data[10] = {8,10,6,-2,10,7,1,100,1,3};
int cari,index;
int ketemu=0;
cout<<" Data = 8,10,6,-2,10,7,1,100,1,3 \n ";
cout<<"masukkan data yang ingin dicari = ";
cin>>cari;
for(int i=0;i<10;i++)
{
if(data[i] == cari)
{
ketemu=1;
index = i;
break;
}
}
if(ketemu == 1)
{
cout<<"Data ada!"<<endl;
cout<<"Data terletak di index ke – "<<index;
}
else cout<<"Data Tidak ada!"<<endl;
getch();
}

hasil nya adalah :

Pencarian Biner (binary search)

· Pengertian

Metoda Pencarian Biner ( Binary Search) hanya bisa diterapkan jika data array sudah teruru. pengurutan Array bisa menggunakan jenis sorting descending atau asscending. Kelebihan dari Searching dengan metode Binary Sort adalah Untuk Pencarian data yang jumlahnya banyak, waktu pencarian relatif cepat. selain itu beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah. namun ada pula kekurangannya, yaitu data harus disorting dahulu dan Algoritma lebih rumit, tidak baik untuk data berangkai.

Algoritma dari Binary Sort
Proses yang terjadi pada pencarian dengan metode ini adalah sebagai berikut :
1.Membaca Array data
2.Apabila Array belum terurut maka array diurutkan terlebih dahulu.
3.Menentukan data yang akan dicari
4.Menentukan elemen tengah dari array
5.Jika nilai elemen tengah sama dengan data yang dicari, maka pencarian berhenti.
6.Jika elemen tengah tidak sama dengan data yang dicari maka :
a.Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
b.Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.
ILUSTRASI BINARY SEARCH
Misalkan saya mempunyai data sebagai berikut : 3,1,4,7,25,12,40,78,90,65. Maka data tersebut akan dicek, ternyata setelah dicek datanya belum terurut, maka dengan menggunakan metoda sorting yang sudah ada, maka kita bisa mengurut data tersebut, menjadi : 1,3,4,7,12,25,40,65,78,90
Setelah data tersebut diurutkan maka fungsi binary sort baru mulai bekerja mencari data. berikut cara dari Binary sort mencari data tersebut. misalnya data yang dicari adalah 65. maka pencariannya dijelaskan pada tabel berikut ini :

Pada data range diberi warna Hijau. Pencarian dimulai dari tengah,Kiri dan kanan. rumus untuk Posisi tengahnya adalah ( Posisi Akhir + Posisi Awal )/2. jadi Nilai tengah pada langkah pertama yaitu adalah 12 (berwarna merah) dan nilai targetnya adalah 65 (kuning). Karena nilai data yang dicari > dari data yang ditengah, maka pencarian menjadi dikanan dari nilai tengah. Setelah itu, Maka nilai 12 menjadi awal pencarian, selanjutnya dicari kembali nilai tengah pada range nilai 12 ke kanan sampai pada array dengan nilai 90. ternyata nilai tengahnya adalah 40. kemudian array dari nilai 40 dibandingkan dengan target, ternyata lebih besar, maka pencarian kembali mengarah ke kanan nilai tengah. Array dengan nilai 40 menjadi titik awal pencarian sekarang. dan sekarang nilai tengah nya adalah 65. maka dibandingkan dengan target ternyata sama, maka data sudah Ditemukan.
setiap data di subtree kiri < data root subtree < setiap data di subtree kanan.

Algoritma

class BinaryNode {
      void printInOrder( )‏{
              if( left != null )‏
              left.printInOrder( );   // kiri
              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 :

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, porses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah + 1.
Demikian seterusnya sampai data tengah sama dengan yang dicari.

Algoritma pencarian biner dapat dituliskan sebagai berikut :

Contoh

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

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;
    }         
  }               
}

contoh program search binary :

#include <stdio.h>

int main()
{
    int c, first, last, middle, n, search, array[100];

    printf("Enter number of elements\n");
    scanf("%d",&n);

    printf("Enter %d integers\n", n);

    for ( c = 0 ; c < n ; c++ )
        scanf("%d",&array[c]);

    printf("Enter value to find\n");
    scanf("%d",&search);

    first = 0;
    last = n - 1;
    middle = (first+last)/2;

    while( first <= last )
    {
        if ( array[middle] < search )
            first = middle + 1;
        else if ( array[middle] == search )
        {
            printf("%d found at location %d.\n", search, middle+1);
            break;
        }
        else
            last = middle - 1;

        middle = (first + last)/2;
    }
    if ( first > last )
        printf("Not found! %d is not present in the list.\n", search);

    return 0;
}

hasil nya adalah :

Contoh Lainnya :

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

int binary_s(int array[], int size, int elemen)
{
  int awal = 0;
  int akhir = size-1;
  int nilaiTengah;
  while (nilaiTengah<=size  && awal<=akhir)
  {
  nilaiTengah = (awal+akhir)/2;
  if (array[nilaiTengah]==elemen)
   return 1;
  else if (elemen<array[nilaiTengah])
   akhir = nilaiTengah-1;
  else
   awal = nilaiTengah+1;
  }
  return 0;
}

int main()
{
  int size=10;
  int data[10]={2, 3, 5, 6, 12, 44, 56, 65, 73 ,81} ;
  cout<<"Data Array"<<endl;
  int i, cari, hasil;

  for(i=0;i<size;i++)
  cout<<data[i]<<"  ";
  cout<<endl<<"masukkan data yang ingin anda cari: ";cin>>cari;
  hasil = binary_s(data, size, cari);
  if (hasil==0)
   cout<<"Nilai tidak ditemukan";
  else
   cout<<"Nilai ditemukan";
  getch();
}

hasil nya adalah :

contoh lain nya :

#include<iostream.h>
#include<conio.h>
int data[10] = {1,3,4,7,12,25,40,65,78,90};  //variabel global
int binary_search(int cari)
{
int l,r,m;
int n = 10;
l = 0;
r = n-1;
int ketemu = 0;
while(l<=r && ketemu==0)
{
m = (l+r)/2;
if( data[m] == cari )
ketemu = 1;
else
if (cari < data[m])
r = m-1;
else l = m+1;
}
if(ketemu == 1) return 1; else return 0;
}
void main()
{
clrscr();
int cari,hasil;
cout<<"data =  1,3,4,7,12,25,40,65,78,90 \n";
cout<<"masukkan data yang ingin dicari = ";
cin>>cari;
hasil = binary_search(cari);
if(hasil == 1)
{
cout<<"Data ada!"<<endl;
}
else
if(hasil == 0)
cout<<"Data Tidak ada!"<<endl;
getch();
}

Algoritma Pencarian (Searching)

Jumat, 23 Januari 2015