Searching

Sequental Search dan Binary Search


A.              Squental search

Adalah 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. Pencarian berurutan menggunakan prinsip sebagai berikut : data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.

B.               Binary search

Sebuah algoritma pencarian biner (atau pemilahan biner) adalah sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (array) linear, dengan menghilangkan setengah data pada setiap langkah, dipakai secara luas tetapi tidak secara ekslusif dalam ilmu Komputer. 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. Sebuah pencarian biner adalah salah satu contoh dari algoritma divide and conquer (atau lebih khusus algoritma decrease and conquer) dan sebuah pencarian dikotomi (lebih rinci di Algoritma pencarian).
Penerapan terbanyak dari pencarian biner adalah untuk mencari sebuah nilai tertentu dalam sebuah list terurut. Jika dibayangkan, pencarian biner dapat dilihat sebagai sebuah permainan tebak-tebakan, kita menebak sebuah bilangan, atau nomor tempat, dari daftar (list) nilai.
Pencarian diawali dengan memeriksa nilai yang ada pada posisi tengah list; oleh karena nilai-nilainya terurut, kita mengetahui apakah nilai terletak sebelum atau sesudah nilai yang di tengah tersebut, dan pencarian selanjutnya dilakukan terhadap setengah bagian dengan cara yang sama.

Binary Search dengan C++

Pencarian Biner (Binary Search) dilakukan untuk :

•     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.

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

•     Syarat utama untuk pencarian biner adalah data di dalam tabel harus sudah terurut, misalkan terurut menaik.

Keunggulan Binary Search 

Keunggulan utama dari algoritma binary search adalah kompleksitas 

algoritmanya yang lebih kecil daripada kompleksitas algoritma sequential search. Hal ini menyebabkan waktu yang dibutuhkan algoritma binary search dalam mencari sebuah record dalam sebuah tabel lebih kecil daripada waktu yang dibutuhkan algoritma sequential search

===============================================================

Contoh Program Squental Search :

#include <conio.h>
#include <iostream.h>
main(){
int c,i,posisi;
int A[20]={3,2,4,10,20,1,5,8,7,9,6,5,11,12,14,13,16,15,17,19};


cout<<"Data : ";
for(i=0;i<20;i++){
 cout<<A[i]<<" ";
}

cout<<"\nData yang ingin dicari : ";
cin>>c;
i=0;
posisi=0;
while(i<19 && A[i]!=c){
 i++;
}
if (A[i]!=c){
 cout<<"Maaf data yang dicari tidak ada";
}else if(posisi=i+1)
   cout<<"ditemukan pada posisi ke "<<posisi;
getch();
}

===============================================================

Contoh Program Binary Search :

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

main ()
{
    int jd, cari,no, kiri,kanan,tengah,data[50];

   cout<<"\n\t\t *************************************** \n";
   cout<<"\t\t | \t\t\t\t       | \n";
   cout<<"\t\t | \t     Proses Pencarian \t       | \n";
   cout<<"\t\t | Menggunakan Algoritma Binary Search | \n";
   cout<<"\t\t | \t\t\t\t       | \n";
   cout<<"\t\t *************************************** \n\n\n";

   cout<<" Input Jumlah Data  : ";
   cin>>jd;

   cout<<endl;
    for (no=0;no<jd;no++)
    {
        cout<<" Input Data Ke-"<<(no+1)<<"    : ";
       cin>>data[no];
    }

   cout<<endl;
    cout<<" Input Nilai Dicari : ";
    cin>>cari;

    kiri=0;
    kanan=jd-1;
    tengah=(kanan-kiri)/2;

    while ((data[tengah]!=cari) && (kiri>=0)&& (kanan<jd) && (kanan>=kiri))
    {
        if (cari>data[tengah])
       {
           kiri=tengah+1;
       }
       else if (cari<data[tengah])
       {
           kanan=tengah-1;
       }
       tengah=kiri+(kanan-kiri)/2;
    }

   cout<<endl;
   if (data[tengah]==cari)
    {
        cout<<" Keterangan         : Data Ditemukan";
    }
    else
    {
        cout<<" Keterangan         : Data Tidak Ditemukan";
    }

    getch();
}


please visit the link :
http://www.stikom-bali.ac.id/