ALGORITMA PENCARIAN

Pencarian (searching) merupakan tindakan untuk mendapatkan suatu data. Untuk keperluan mencari data, terdapat beragam algoritma pencarian (search algorithm). Yang dimaksud dengan algoritma pencarian adalah “algoritma yang menerima sebuah argumen a dan mencoba untuk menemukan rekaman yang memiliki kunci a”Sebagai contoh , dikehendaki untuk mendapatkan mahasiswa dengan nomor urut 9834567. Hasilnya adalah rekaman yang berisi data mahasiswa tersebut; yang barangkali berisi nama, alamat, tanggal lahir, dan nama program studi.

Sequential Search adalah teknik pencarian data dimana data dicari secara urut dari depan ke belakang atau dari awal sampai akhir. Kelebihan dari proses pencarian secara sequential ini jika data yang dicari terletak didepan, maka data akan ditemukan dengan cepat. Tetapi dibalik kelebihannya ini, teknik ini juga memiliki kekurangan. Pertama, jika data yang dicari terletak dibelakang atau paling akhir, maka akan membutuhkan waktu yang lama dalam proses pencariannya. Kedua, beban komputer akan semakin bertambah jika jumlah data dalam array sangat banyak.

contoh algoritma pencarian sequential

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

int cari_linear(int array[],int ukuran, int cari);

void main()
{
  const int ukuran=10;
  int array[ukuran]={25,36,2,48,0,69,14,22,7,19};
  cout<<"Isi dari array: "<<endl;
  for(int i=0;i<ukuran;i++)
   cout<<" "<<array[i];

  int cari;
  int tanda=-1;
  cout<<"\n\nMasukkan data yang dicari: ";
  cin>>cari;

  tanda= cari_linear(array,ukuran,cari);
  if (tanda!=-1)
  cout<<"\n\nData tersebut ditemukan pada posisi: array["<<
  tanda<<"],"<<" atau deret ke-"<<(tanda+1);
  else
  cout<<"\nData tersebut tidak ditemukan ";
  getch();
}

int cari_linear(int array[],int ukuran,int cari)
{
  int tanda=-1;
  for(int i=0;i<ukuran;i++)
  {
   if(cari==array[i])
   {
     tanda=i; break;
   }
  }
  return tanda;
}

ALGORITMA PENCARIAN BINER (BINARY SEARCH)

Pencarian Biner (Binary Search) pada array yang sudah terurut

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.

ALGORITMA   PENCARIAN BINER

Kamus

      Const N : integer = 8  { misalkan jumlah elemen array maksimum = 8 }

      Type A = array [ 1 ..... N ] of integer

      Cari, BatasAtas, BatasBawah, Tengah : Integer

      Ketemu : boolean

ALGORITMA

         Input (cari) { meminta nilai data yang akan dicari}

         BatasAtas     ¬  1 { indeks array dimulai dari 1 }

         BatasBawah     ¬   N    

         Ketemu   ¬  False

         While (BatasAtas < BatasBawah) and (not ketemu) do

               Tengah ¬   (BatasAtas  + BatasBawah) div 2

               If A [Tengah] = cari then

                  Ketemu ¬ true

                           Else

                                 If ( A [Tengah]  < cari ) then { cari di bagian kanan }

                                       BatasAtas ¬ Tengah + 1

                                 Else

                                       BatasBawah ¬ Tengah – 1 { cari di bagian kiri }

                                 Endif

                           Endif

         EndWhile

         If (ketemu) then

                     Output ( ‘Data berada di index nomor’, Tengah )

         Else     Output ( ‘Data tidak ditemukan’ )

End if

            ALGORITMA PENCARIAN LAINNYA

Pencarian Interpolasi
Melakukan pencarian dengan membagi medan pencarian menjadi dua bagian yang tidak seimbang, namun diestimasi berdasarkan kunci yang dicari
Keuntungan : jauh lebih efektif daripada sequential maupun binary search
Kekurangan : hanya dapat dilakukan pada rekaman-rekaman yang telah terurut berdasarkan kunci yang dicari dan kuncinya harus bertipe data numeric.

Algoritma Pencarian Interpolasi
Mulai
 1ßAwal
Akhir  nß
while Awal <  (Kunci(Cari) – Kunci(Awal)) / (Kunci(Akhir)ßAkhir Rasio   Awal + Rasio * (Akhir – Awal) if Kunci(Cari) =ß– Kunci(Awal)) Berikut   Berikut goto 16 else if Kunci(Cari)ßKunci(Berikut) Hasil  > Kunci(Berikut)
 Berikut + 1ßAwal
 Berikut - 1ßelse Akhir
end if
end while
 tidak ketemußHasil
Selesai

Pencarian List

Algoritma pencarian list mungkin adalah algoritma pencarian paling dasar. Tujuannya adalah mencari sebuah elemen dari sebuah himpunan dengan suatu kunci (kemungkinan memuat informasi yang terkait dengan kunci). Oleh karena hal ini adalah masalah yang lazim dalam ilmu komputer, kompleksitas komputasi algoritma-algoritma tersebuh telah dipelajri dengan baik. Algoritma paling sederhana adalah pencarian linear, yang secara sederhana melihat setiap elemen dari list secara berurutan. Waktu pengerjaan algoritma ini adalah O(n), dimana n adalah banyaknya elemen dalam list, dan dapat digunakan langsung pada list yang belum diproses. Algoritma pencarian list yang lebih canggih adalah pencarian biner; waktu pengerjaannya adalah O(log n). Waktu pengerjaannya jauh lebih baik daripada pencarian linear untuk list yang memiliki data banyak, tetapi sebelum dilakukan pencarian list terlebih dahulu harus terurut (lihat algoritma pengurutan) dan juga harus dapat diakses secara acak (pengaksesan acak).

 Algoritma Grover adalah sebuah algoritma kuantum yang menawarkan percepatan kuadrat dibandingkan pencarian linear klasik untuk list tak terurut.

Algortima pencarian brute-force atau pencarian naif/uninformed menggunakan metode yang sederhana dan sangat intuitif pada ruang pencarian,

 Sedangkan algoritma pencarian informed menggunakan heuristik untuk menerapkan pengetahuan tentang struktur dari ruang pencarian untuk berusaha mengurangi banyaknya waktu yang dipakai dalam pencarian.