Pengertian Tentang Searching & Contoh Program-nya

SEARCHING (PENCARIAN)

Ketika menggunakan array untuk memecahkan suatu permasalahan di dalam program, mungkin suatu saat anda akan mencari elemen tertentu di dalam array. Hal ini sering dilakukan dengan cara menggunakan suatu kunci pencarian dan membandingkan semua elemen yang ada dalam array yang digunakan.Proses pencarian suatu elemen di dalam array disebut searching.

Ada beberapa pencarian yang akan kita uraikan disini:

* Pencarian Beruntun (Sekuensial Search)

* Pencarian Bagi dua (Binary Search)

==>Pencarian Beruntun (Sekuensial Search)

Konsep :

 membandingkan setiap setiap elemen larik satu per satu secara urut(beruntun), mulai dari elemen pertama sampai dengan elemen yang terakhir. Ada 2 macam pencarian beruntun,yaitu pencarian pada  array yang sudah terurut, dan pencarian pada array yang belum terurut.

Langsung saja kita ke contoh program :

Hasil setelah program dijalankan :

==>Binary Search

Binary search adalah sebuah algoritma pencarian dengan cara membagi data menjadi dua bagian setiap kali terjadi proses pencarian untuk menemukan nilai tertentu dalam sebuah larik (array) linear.

 Sebuah pencarian biner mencari nilai tengah (median/mid), melakukan sebuah  pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama.

 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.

 -Beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah.

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

 Kekurangan binary search yaitu data harus disorting dahulu. 

Berikut ilustrasi pencarian menggunakan binary search dengan bantuan tabel. Misalkan kita mempunyai data sebagai berikut : {1, 2, 3, 4, 5, 6, 7, 8}. Data yang kita cari adalah 7. 

Untuk menyelesaikan soal diatas, maka diselesaikan dengan cara berikut : 

Diketahui nilai kiri=0 (nilai awal array) dan nilai kanan = 8.

 Rumus posisi tengah adalah (kanan + kiri)/2. Jadi Nilai tengah pada langkah pertama yaitu (8+0)/2=4. Jika dimasukkan kedalam tabel akan menunjuk nilai 4 (berwarna orange). Kemudian dibandingkan dengan nilai yang dicari (3), karena nilai yang dicari lebih besar dari data ditengah maka pencarian di alihkan ke sebelah kanan dengan batas kiri (awal pencarian) merupakan nilai tengah yakni 4.

 Nilai tengah pada langkah kedua yaitu (8+4)/2=6. Jika dimasukkan ke dalam tabel maka akan menunjuk nilai 6 (berwarna orange). Kemudian dibandingkan lagi dengan nilai yang dicari (7), karena nilai yang dicari masih lebih besar dari nilai tengah, maka pencarian dialihkan lagi ke kanan dengan batas kiri (awal pencarian) merupakan nilai tengah yakni 6.

 Nilai tengah pada langkah ketiga yaitu (8+6)/2=7. Jika dimasukkan ke dalam tabel maka akan menunjuk nilai 7 (berwarna kuning). 

Kemudian dibandingkan lagi dengan nilai yang dicari (7), setelah dibandingkan nilainya sama, maka pencarian selesai dengan keterangan data ditemukan.

 Untuk lebih jelasnya lagi perhatikan algoritma deskriptif binary search berikut :

 1. Input seluruh data kedalam array .

2. Tentukan algoritma untuk sorting array ascending (kecil ke besar).

3. Input data yang dicari.

 4. Tentukan nilai kiri, kanan, dan tengah dengan rumus :

 a. Kiri sama dengan nol

 b. Kanan lebih kecil dari jumlah data

 c. Tengah sama dengan hasil kanan dikurangi hasil kiri dibagi dua.

 5. Jika elemen tengah tidak sama dengan data yang dicari, maka :

 a. Jika elemen tengah lebih besar dari data yang dicari, maka pencarian dilakukan pada  setengah array pertama. Caranya dengan menggunakan perintah kiri sama dengan tengah ditambah satu.

 b. Jika elemen tengah lebih kecil dari data yang dicari, maka pencarian dilakukan pada setengah array berikutnya. Caranya dengan menggunakan perintah kanan sama dengan tengah dikurangi satu.

c. Tengah sama dengan kiri ditambah (kanan - kiri) dibagi dua.

6. Jika elemen tengah sama dengan data yang dicari, maka data ditemukan. Sedangkan jika elemen tengah tidak sama dengan data yang dicari, maka data tidak ditemukan.

Contoh Program Binary search:

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

int main () {

 int n, angka[12], kiri, kanan, tengah, temp, key;

 bool ketemu = false;

 cout<<"Masukan jumlah data : ";

 cin>>n;

 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<<"Data yang telah diurutkan adalah : ";

 for(int i=0; i<n; i++)

 {

  cout<<angka[i]<<" ";

 }

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

  getch();

  return 0;

 }

 

Hasil setelah program dijalankan:

Sekian artikel tentang Searching pada bahasa C++ , semoga bermanfaat .

Sumber:

1. http://www.academia.edu/8572021/Modul_Struktur_Data_C_STMIK_AMIKOM_YOGYAKARTA

2. Referensi dari Buku : ALGORITMA DAN PEMROGRAMAN DENGAN C++ (edisi II)

Oleh : Andri Kristanto,S.Kom