Materi Searching

Pengertian Searching

Searching adalah metode pencarian informasi dalam suatu aplikasi, dengan suatu kunci (key). Pencarian diperlukan untuk mencari informasi khusus dari table pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui. Pencarian selalu dinyatakan dengan referensi pada adanya sekelompok data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut table. Pada metode searching (pencarian) ada 2 teknik yang digunakan yaitu:

Pencarian sekuensial (sequential search) dan

Pencarian biner (Binary search).

Pengertian Sequential search

Pencarian sekuensial (sequential search) atau sering disebut pencarian linier menggunakan prinsip sebagai berikut: data yang ada di bandingkan satu persatu secara berurutan dengan yang dicari. Pada dasarnya, pencarian ini hanya melakukan pengulangan dari 1 sampai dengan jumlah data. Pada setiap perulangan, di bandingkan data ke-i dengan yang dicari. Apabila sama , berarti data telah ditemukan . Sebaliknya apabila sampai akhir pengulangan , tidak ada yang sama berarti data tidak ada. 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.. Algoritma pencarian berurutan dapat dituliskan sebagai berikut:

Mencari data 5 dari array [,1,2,4,3,5]

maka akan mengecek dari awal sampai data ketemu, jadi akan di periksa satu persatu , 

dengan cara membandingkan seperti ini 

apakah 5 = 1 False apakah 5 = 2 False apakah 5 = 4 False apakah 5 = 3 False apakah 5 = 5 True

jika ada ada di tengah maka akan berhenti ketika kondis menjadi True, dan tidak akan di ualang lagi  contoh  kita mencari data 5 dari array [,1,2,5,3,4]

apakah 5 = 1 False apakah 5 = 2 False apakah 5 = 5 True

Jika data sudah ditemukan maka tidak akan di proses dan program akan berhenti.

Contoh:

didefinisikan diatas adalah aray X

x [0] = 100

x [1] = 50

x [2] = 40

x [3] = 66

x [4] = 20
x [5] = 10

kita cari dengan cara mengurutkan dengen perulangan 

i=0; while(i <= 5){      if(x[i]==40){         alert("Data Ketemu");      }else{          i++;       } }

Dari perulangan di atas akan mengecek satu persatu data array dan menyamakannya dengan data yg akan di cari.

Pengertian Binery Search

Binary search adalah algoritma pencarian untuk data yang terurut. Pencarian dilakukan dengan cara menebak apakah data yang dicari berada ditengah-tengah data, kemudian membandingkan data yang dicari dengan data yang ada ditengah. Bila data yang ditengah sama dengan data yang dicari, berarti data ditemukan. Namun, bila data yang ditengah lebih besar dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan berada disebelah kiri dari data tengah dan data disebelah kanan data tengah dapat diabai. Upper bound dari bagian data kiri yang baru adalah indeks dari data tengah itu sendiri. Sebaliknya, bila data yang ditengah lebih kecil dari data yang dicari, maka dapat dipastikan bahwa data yang dicari kemungkinan besar berada disebelah kanan dari data tengah. Lower bound dari data disebelah kanan dari data tengah adalah indeks dari data tengah itu sendiri ditambah 1. Demikian seterusnya.

Merupakan salah satu metode pencarian yang menangani kasus terburuk (worst case) pada pencarian secara berurutan. Proses pencarian binary search hanya dapat dilakukan pada data yang sudah berurutan. Cara pencarian binary ini adalah dengan membagi dua elemen penampung nilai dan membandingkan nilainya Algoritma dari binary search adalah:

Tentukan posisi awal = 0 dan posisi akhir = N – 1

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

Bandingkan data yang dicari dengan elemen posisi tengah

Jika data yang dicari sama maka catat posisi dan cetak kemudian berhenti

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

Jika nilai datanya 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 Program:

#include <iostream> #include <conio.h> int binary_s(int array[], int size, int elemen);  int main()  {  int size=10;  int data[10]={2, 3, 5, 6, 12, 44, 56, 65, 73 ,81} ; cout<<"Data Array"<<endl; int i; for(i=0;i<size;i++) cout<<data[i]<<" "; cout<<endl<<endl<<"masukkan data yang ingin anda cari: "; int cari; cin>>cari; // pencarian int hasil;  hasil = binary_s(data, size, cari);  if (hasil==0)  cout<<"Nilai tidak ditemukan"; else cout<<"Nilai ditemukan"; getch(); } int binary_s(int array[], int size, int elemen) { int awal = 0; int akhir = size-1; int nilaiTengah = (awal+akhir)/2; 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;

Di bawah ini merupakan fungsi untuk mencari data menggunakan pencarian biner. 

int BinarySearch(int x) {      int L = 0, R = Max-1, m;      bool ditemukan = False;      while((L <= R) && (!ditemukan))      {           m = (L + R) / 2;           if(Data[m] == x)                ditemukan = True;           else if (x < data[m])                R = m - 1;           else                L = m + 1;      }      if(ditemukan)           return m;      else           return -1; }

Contoh Program:

#include <iostream> #include <conio.h> main () { int angka[‘n’]; int n, kiri, kanan, tengah, temp, key; bool ketemu = false; cout<<“\n==========================================\n”<<endl; cout<<”                    BINARY SEARCHING”<<endl; cout<<“\n==========================================\n”<<endl; cout<<“\n\n”; cout<<“Masukan jumlah data : “; cin>>n; cout<<endl; for(int i=0; i<n; i++) { cout<<“Angka ke – [“<<i<<“] : “; cin>>angka[i]; } for (int i=0; i<n; i++){ for(int j=0; j<n-i-1; j++){ if(angka [j] > angka [j+1]) { temp=angka[j]; angka[j]=angka[j+1]; angka[j+1]=temp; } } } cout<<“\n\n”; cout<<“Data yang telah diurutkan adalah: “; for(int i=0; i<n; i++) { cout<<angka[i]<<” “; } cout<<“\n\n”; cout<<endl; cout<<“PENCARIAN DATA”; cout<<“\n Masukan angka yang dicari : “; cin>>key; kiri=0; kanan=n-1; while(kiri<=kanan) { tengah=(kiri + kanan)/2; if(key == angka[tengah]) { ketemu=true; break; } else if (key < angka [tengah]) { kanan = tengah -1; } else { kiri = tengah +1; } } if (ketemu == true) cout<<“Angka ditemukan!”; else cout<<“Angka tidak ditemukan”; cout<<endl; cout<<“\n\n”; cout<<“Tekan enter untuk keluar!!!!!!”<<endl; getch(); }

Fungsi diatas akan mengembalikan indeks dari data yang dicari. Apabila data tidak ditemukan maka fungsi diatas akan mengembalikan nilai –1. Jumlah pembandingan minimum pada pencarian biner adalah 1 kali, yaitu apabila data yang dicari tepat berada di tengah-tengah. Jumlah pembandingan maksimum yang dilakukan dengan pencarian biner dapat dicari menggunakan rumus logaritma, yaitu: C = 2log (N)