Searching

Pencarian sebenarnya merupakan hal-hal yang sering dilakukan setiap hari. Sebagai contoh saat kita menggunakan kamus untuk mencari kata-kata dalama Bahasa Inggris atau bahasa lainnya. Contoh lainnya adalah saat seorang guru menyuruh murid-muridnya untuk membuka suatu halaman tertentu di dalam buku pelajaraan dan masih banyak contoh lainnya dalam kehidupan sehari-hari.

Pencarian Data dapat juga disebut Table look-up atau storage and retrieval information merupakan suatu proses untuk mengumpulkan sejumlah informasi didalam perangkat komputer dan mencari kembali informasi yang dibutuhkan secepat mungkin.

Algoritma pencarian (searching) merupakan algoritma yang mendapatkan sebuah argument kunci dan dengan langkah-langkah tertentu akan mencari sebuah argument dengan kunci tersebut. Dalam pencarian akan ada dua kondisis, yaitu kondisi dimana data ditemukan dan kondisi dimana data yang dicari tidak ditemukan.

Ada dua macam metode pencarian yaitu pencarian sekuensial dan pencarian biner.

1. Squential Searching

Pencarian ini merupakan metode yang paling sederhana, sering juga disebut sebagai  pencarian linier. Pencarian berurutan (Sequential Searching) menggunakan prinsip dimana data yang ada dibandingkan satu per satu secara berurutan dengan data yang dicari sampai data tersebut ditemukan atau tidak ditemukan.

Pencarian ini melakukan pengulangan dari 1 sampai dengan jumlah data, pada setiap pengulangan dibandingkan setiap data ke-i dengan data yang dicari. Apabila data tersebut sama, maka data telah ditemukan. Sedangkan jika sampai akhir pengulangan data tidak ditemukan  yang sama, berarti data tidak ditemukan.

Proses Pencarian Berurutan dapat kita sederhanakan menjdai beberapa point :

• Data yang ada dibandingkan satu per satu secara berurutan dengan yang dicari sampai data tersebut ditemukan atau tidak ditemukan.
•  Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data.
• Pada setiap pengulangan, dibandingkan data ke-i dengan yang dicari.
• Apabila sama, berarti data telah ditemukan. Sebaliknya apabila sampai akhir pengulangan tidak ada data yang sama, berarti data tidak ada.

Algoritma pencarian berurutan dapat ditulis 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 tidak data tidak ditemukan

Contoh program sederhana dalam C :

#include <stdio.h>

#include <conio.h>

void main(){

   int data[8] = {8,10,6,-2,11,7,1,100};

   int cari;

   int temu=0;

   printf("Masukan data yang ingin dicari = ");

   scanf("%d",&cari);

   for(int i=0;i<8;i++){

                if(data[i] == cari) temu=1;

   }

   if(temu==1) printf("Data Ditemukan!\n"); 

 else printf("Data Tidak Ditemukan!\n");

 getch();

 return 1;

}

   2. Binary Seacrh

Ada kondisi yang harus dipenuhi dalam Binary Seacrh yaitu data yang ada harus sudah dalam keadaan  terurut. Dengan kata lain, apabila data belum terurut maka Binary Seacrh atau pencarian biner tidak bisa dilakukan, oleh karena itu biasanya ada printah-printah untuk mengurutkan data terlebih dahulu sebelum masuk ke printah pencarian biner.

Prinsip dalam pencarian biner dapat dijelaskan sebagai berikut, pertama diambil posisi awal 0 dan posisi akhir = N – 1, selanjutnya mencari posisi data tengah dengan rumus (posisi awal + posisi akhir)/2. Kemudian data yang dicari dibandingkan dengan data tengah. Jika kondisi data yang dibandingkan lebih kecil, maka proses dilakukan kembali tetapi posisi akhir dianggap sama dengan posisi tengah -1. Jika kondisi data yang dibandingkan lebih besar, proses dilakukan kembali tetapi posisi awal dianggap sama dengan posisi tengah +1, demikian seterusnya sampai data tengah sama dengan data yang dicari.

Untuk lebih jelasnya, silahkan lihat contoh dibawah :

Misalnya ingin mencari data 16 pada sekumpulan data berikut,

 

 

   Mula-mula cari data tengah, dengan rumus (0 + 9)/2 = 4, maka data tengah adalah data ke-4 yang berisi data 14. Data yang dicari yaitu 16, bandingkan dengan data tengah. Karena 16>14, berarti proses dilakukan kembali hanya saja kondisi awal dianggap sama dengan posisi tengah + 1  yaitu posisi ke-5.

  Data tengah didapat dengan rumus (5 +9)/2 = 7, berada di posisi ke-7, dengan data 22. Data yang sedang dicari yaitu 16, maka data yang dicari dibandingkan dengan data tengah. Karena 16<22, maka proses dilanjutkan kembali tetapi posisi akhir dianggap sama dengan posisi tengah – 1, yaitu posisi ke-6.

   Data tengah didapatkan dari (5 +6)/2 = 5, maka posisi tengah berada di posisi ke-5 dengan data 16, data yang dicari dibandingkan dengan data tengah dan ternyata sama, maka data ditemukan pada posisi/indeks ke-5.

   Pencarian Biner akan berakhir apabila data yang dicari ditemukan atau posisi awal lebih besar daripada posisi akhir. Jika posisi awal lebih besar dari posisi akhir berarti data tidak ditemukan.

  Untuk contoh lebih jelasnya, misal data yang ingin dicari adalah 15, proses pencarian hampir sama dengan proses pencarian data 16. Tetapi setelah posisi awal 5 dan posisi akhir 6, data tidak ditemukan 15<16, maka posisi akhir menjadi posisi tengah – 1 atau pada indeks ke-4 sedangkan posisi awal pada indeks ke-5.

 

 

Dapat diartikan bahwa posisi awal lebih besar dari posisi akhir yang artinya data tidak ditemukan.

Algoritma pencarian biner dapat dituliskan sebagai berikut :

1. Awal ← 0
2. Akhir ← N - 1
3. Ketemu ← false
4. Selama (Awal <= Akhir) dan (tidak ketemu) kerjakan baris 5 sampai dengan 8  
5. m ← (Awal + Akhir) / 2
6. Jika (Data[m] = x) maka ketemu ← true
7. Jika (x < Data[m]) maka Akhir ← m – 1
8. Jika (x > Data[m]) maka Awal ← m + 1
9. Jika (ketemu) maka m adalah indeks dari data yang dicari, jika tidak data tidak ditemukan.

 Contoh Program Pencarian Biner :

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;

}         

}                     

}