Searching ( Sequential search dan Binary search ) beserta Contohnya

Nama  : Agung Wijaya Kusuma

NIM     : 140010222

Kelas   : AB141

Nama Dosen : Ida Bagus Kadek Surya Arnawa. S.Kom

Nama Asisten Dosen : Steven Anthony

     F.    Searching

Pencarian (Searching) merupakan tindakan untuk mendapatkan suatu data dalam kumpulan data berdasarkan satu kunci (key) atau acuan data dan pencarian data dengan cara menelusuri data-data tersebut. Tempat pencarian data dapat berupa array pada external memori, dan bisa juga di dalam internal memori. .
Pada umumya dikenal tiga metode Searching , antara lain : Sequential Search, Binary Search,  dan Interpolation Search. Tetapi saya akan menjelasakan tentang Sequential Search dan Binary Search saja.

     1.    Sequential Search

Sequential Search (pencarian beruntun) adalah proses membandingkan setiap elemen array satu per satu secara beruntun yang dimulai dari elemen pertama hingga elemen yang dicari ditemukan atau hingga elemen terakhir dari array.

Contoh : Diberikan satu array nilai dengan banyak elemen 8 seperti berikut :

10

13

9

3

25

65

13

30

       1               2                3               4              5             6               7              8

Misalkan nilai yang dicari adalah: X = 13

Kalau yang diharapkan hanya menyatakan ada atau tidak maka pemeriksaan di lakukan terhadap 10 dan 13 maka tampil pesan "13 ditemukan".


Kalau yang diharapkan adalah menampilkan seluruh data yang sama dan posisinya maka pemeriksaan dilakukan terhadap seluruh data 10, 13, 9, 3, 25, 65, 25, 13, dan 30. Pada saat pemeriksaan di lakukan dan ternyata sama maka posisi data yang sama tersebut akan di simpan dalam variabel juga (tipe array) dan hitung banyaknya data yang sama. Sehingga akan tampil pesan "13 ditemukan sebanyak 2 yaitu pada posisi 2 dan 7". 

Contoh Sorting Sequensial Search pada koding pemrograman:

/* Program Sequential Search */

#include <iostream.h>

#include <conio.h>

main()

{

            int Nilai[20];

            int i, N, Bilangan;

            bool ketemu;

cout<<”Masukkan Banyaknya Bilangan  : “;

cin>>N;

//Membaca elemen Array

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

{

            cout<<”Masukkan elemen ke-“<<i<<” :  “;

            cin>>Nilai[i];

}

//Mencetak elemen Array

cout<<endl;

cout<<”Deretan Bilangan : “;

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

cout<<Nilai[i]<<” “;

cout<<endl;

cout<<”Masukkan Bilangan yang akan Dicari : “;

cin>>Bilangan;

//melakukan pencarian

i=0;

do

{

            if(Nilai[i]==Bilangan)

            ketemu  = true;

            i++;

}

while( ! (ketemu));

if(ketemu)

cout<<”Bilangan “<<Bilangan<<” ditemukan “;

else

cout<<”Bilangan “<<Bilangan<<”tidak ditemukan”;

getch();

} 

Jika di compile dari coding Searching Sequential Search, maka akan tampak seperti gambar di bawah ini:

  

     2.    Binary Search

Binary Search adalah metode pencarian suatu data atau elemen didalam suatu array dengan kondisi data dalam keadaan terurut. Proses pencarian binary search hanya dapat dilakukan pada kumpulan data yang sudah diurutkan terlebih dahulu 

( menaik atau menurun ). Prinsip dari binary search terhadap N elemen dapat dijelaskan sebagai berikut :

a.    Tentukan posisi awal = 0 dan posisi akhir = N-1

b.    Hitung posisi tengah = (posisi awal + posisi akhir)/2.

c.    Bandingkan data yang dicari dengan elemen posisi tengah.

·         Jka sama maka catat posisi dan cetak kemudian berhenti

·         Jika lebih besar maka akan dilakukan pencarian kembali ke bagian kanan dengan posisi awal = posisi tengah +1 dan posisi akhir tetap kemudian ulangi mulai poin 2.

·         Jika lebih kecil maka akan dilakukan pencarian kembali ke bagian kiri dengan nilai posisi awal tetap dan nilai posisi akhir = posisi tengah -1 kemudian ulangi mulai poin 2

Contoh : Misalnya kita mempunyai deretan data dalam array nilai sebanyak 10 elemen dan akan dilakukan pencarian data 87 terhadap array. 

Nilai[0..9] = 12,45,23,87,90,55,15,25,40,21

Urutkan elemen array secara menaik, sehingga diperoleh:
Nilai[0..9] = 12,15,21,23,25,40,45,55,87,90

Data yang akan dicari = 87(bilangan)

Tentukan nilai awal = 0, akhir = N-1=9

Hitung tengah = (9+0)/2=4

Bandingkan Bilangan < Nilai[tengah]->87=25->false

Bandingkan Bilangan < Nilai[tengah]->87<25->false

Bandingkan Bilangan < Nilai[tengah]->87>25->true maka pencarian dilakukan ke sebelah kanan dengan nilai awal = tengah+1 = 5

Karena awal masih lebih kecil dari akhir maka ulangi kembali mulai menghitung tengah

Hitung tengah = (9+5)/2=7

Bandingkan Bilangan  < Nilai[tengah] ->87=55->false

Bandingkan Bilangan < Nilai[Tengah]->87<55->false

Bandingkan Bilangan < Nilai[tengah]->87>55->true maka pencarian dilakukan ke sebelah kanan dengan nilai awal = tengah+1 = 8

Karena awal masih lebih kecil dari akhir maka ulangi kembali mulai menghitung tengah

Hitung tengah = (9+8)/2 = 8

Bandingkan Bilangan < Nilai[tengah]->87=87->true


Karena sudah ditentukan hasil yang kita cari maka proses pencarian berhenti.

Contoh Searching Binary Search pada koding pemrograman:

 :

/* Program pencarian dengan Binary Search*/

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#include <iomanip.h>

void main()

{

            //deklarasi variabel

            int Nilai[20];

            int i, j, N;

            int temp, awal, akhir, tengah, Bilangan;

//proses penginputan data

cout<<”Banyak Bilangan : “;

cin>>N;

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

            {

                        cout<<”Elemen ke-“<<i<<”  =  “;

                        cin>>Nilai[i];

}

cout<<endl;

cout<<”Elemen sebelum diurut = “;

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

{

cout<<setw(3)<<Nilai[i];

}

//proses pengurutan data

for(i=0;i<N-1;i++)

{

                        for(j=i+1;j<N;j++)

{

                                    if (Nilai[i] > Nilai[j])

{

                                                temp = Nilai[i];

                                                Nilai[i]=Nilai[j];

                                                Nilai[j] = temp;

}          

}          

}

cout<<endl;

cout<<”Elemen seteleh diurut = “;

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

{

cout<<setw(3)<<Nilai[i];

}

cout<<endl;

cout<<”Index Elemen : “;

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

{

cout<<setw(3)<<i;

}

cout<<endl;

cout<<”Masukkan data yang akan anda cari : “;

cin>>Bilangan;

//proses pencarian data

awal = 0;

akhir = N-1;

do

{

            tengah = (akhir + awal)/2;

            if(Bilangan < Nilai[tengah])

{

                        akhir = tengah -1;

}

else

{

                        awal = tengah + 1;

}

}

while ((akhir >= awal) && (Nilai[tengah] != Bilangan));

{

if (Nilai[tengah] == Bilangan)

{

                                    cout<<endl;

                                    cout<<”Data “<<Bilangan<<” ada dalam array “;

                                    cout<<”Pada posisi “<<tengah;

}

else

{

cout<<endl;

cout<<”Data “<<Bilangan<<” tidak ada dalam array “;

cout<<endl;

}

}

getch();

}

Jika di compile dari coding Binary Search, maka akan tampak seperti gambar di bawah ini:

Sumber           : Buku Konsep dan Implementasi Struktur Data dengan C++

Oleh                : Lamhot Sitorus dan David J.M Sembiring, Andi Kristanto, S.Kom

Penerbit           : Andi dan Graha Ilmu