Lompat ke konten Lompat ke sidebar Lompat ke footer

Pencarian (Searching) pada Algoritma

 
Pencarian di perlukan untuk mencari informasi khusus dari tabel pada saat lokasi yang pasti dari informasi tersebut sebelumnya tidak diketahui.  Pencarian selalu dinyatakan dengan referensi pada adanya sekolompok data yang tersimpan secara terorganisasi, kelompok data tersebut kita sebut tabel.  Array memungkinkan untuk menyimpan nilai yang bertipe sama.  Operasi yang umum dalam array adalah Sequential Search dan Binary search. Perbedaan dari kedua teknik ini terletak pada keadaan data.

Contoh penulisan pemrograman menggunakan bahasa C


Pencarian Sequensial (Sequential Search)

Pencarian sequensial digunakan apabila data dalam keadaan acak atau tidak terurut.  Pencarian sequensial atau sering disebut Pencarian Linear menggunakan prinsip data yang ada dibandingkan satu persatu secara berurutan dengan data yang dicari.
  • Sequential Search pada Array yang elemen datanya belum terurut menggunakan metode tanpa sentinel dan metode dengan sentinel.
  • Sequential Search pada Arrray yang elemen datanya sudah terurut menggunakan metode tanpa sentinel dan dengan metode sentinel.

Proses pencarian sekuensial data belum terurut tanpa sentinel

  • pada dasarnya pencarian ini hanya melakukan pengulangan dari elemen kesatu (ke-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 yang sama, berarti data tidak ada.


/* SeqSearch_BelumUrut_nonSentinel
diasumsikan Array X sudah ada dan berisi data yang belum terurut, nilai yang dicari adalah Y dan hanya ada satu */

#include <iostream.h>
typedef enum boolean {false=0, true=1};
main()
{
    int X[10]={20,50,10,30,90,60,70,80,40,100};
    boolean found;
    int i,y;
    cout << "nilai yang dicari = ";
    cin >> y;
   found=false;
   i=0;
   while ( (i<10) & (!found) )
   {
        if  (X[i]==y)
              found=true;
        else
              i= i + 1;
    }
    if (found)
       cout << y <<" ditemukan pada index array ke-" << i;
    else
       cout << y  <<" tidak ada dalam Array tersebut":
}



Cara lain untuk pencarian sekuensial pada data Array X[n] adalah dengan menyediakan satu tempat setelah elemen terakhir, yaitu pada X[n-1] dan menyimpan harga yang dicari (misalnya Y) pada posisi tersebut.  Nilai yang dicari pada posisi elemen terakhir tersebut dinamakan sentinel.

Proses pencarian sekuensial data belum terurut dengan sentitel

  • Pada dasarnya pencarian ini sama dengan proses pencarian sekuensial data belum terurut tanpa sentinel yaitu melakukan pengulangan dari elemen kesatu (ke-1) sampai dengan jumlah data.
  • Pada setiap pengulangan, dibandingkan data ke-i, dengan yang dicari
  • apabila sama berarti data telah ditemukan
  • Perbedaannya dengan yang tanpa sentinel adalah ketika data ditemukan tapi data tersebut adalah sentinel berarti data tidak ada.

Contoh Program SeqSearch_BelumUrut_Sentinel {Cara_1)

/* SeqSearch_BelumUrut_Sentinel {Cara_1}
diasumsikan Array X [0..10] sudah ada dan indeks ke 0..9 berisi data yang belum terurut, nilai yang dicari adalah Y dan hanya ada satu, Y diletakkan di indeks ke-10  */

#include <iostream.h>

main()
{
    int X[11]={20,50,10,30,90,60,70,80,40,100};
    int i,y;

    cout << "nilai yang dicari = ";
    cin >> y;

   X[10]=y;
   i=0;
   while ( (X[i] !=y) )
            i= i + 1;
   if  (i>9)
          cout <<" tidak ada " << y << " dalam Array";
    else
       cout << y  <<" tidak ada dalam Array pada indeks ke-": << i;
}


Contoh Program SeqSearch_BelumUrut_Sentinel {Cara_2}

/* SeqSearch_BelumUrut_Sentinel {Cara_2}
diasumsikan Array X [0..10] sudah ada dan indeks ke 0..9 berisi data yang belum terurut, nilai yang dicari adalah Y dan hanya ada satu, Y diletakkan di indeks ke-10  */

#include <iostream.h>
typedef enum boolean {false=0, true=1);

main()
{
    int X[11]={20,50,10,30,90,60,70,80,40,100};
    int i,y;
    boolean =found;
    cout << "nilai yang dicari = ";
    cin >> y;

   X[10]=y;
   found=false;
   i=0;
   while ( (!found )
   {
       if  (X[i]==y) found=true;
       else i+i+1;
   }
   if  (i==10)
          cout <<" tidak ada " << y << " dalam Array";
    else
       cout << y  <<" ditemukan dalam Array pada indeks ke-": << i;
}



Proses pencarian sekuensial data sudah terurut tanpa sentinel

    dimulai dari elemen pertama pada Array, dilakukan perbandingan dengan elaman yang dicari, jika elemen dalam Array masih lebih kecil dari elemen yang dicari maka pencarian diteruskan, jika sudah lebih besar, pencarian dihentikan, dan bisa dipastikan elemen yang dicari memang tidak ada.


    /* SeqSearch_Urut_nonSentinel
    diasumsikan Array X sudah ada dan berisi data yang terurut, nilai yang dicari adalah Y dan hanya ada satu */

    #include <iostream.h>
    typedef enum boolean {false=0, true=1};
    main()
    {
        int X[10]={20,50,10,30,90,60,70,80,40,100};
        boolean found;
        int i,y;
        cout << "nilai yang dicari = ";
        cin >> y;
       found=false;
       i=0;
       while ( (i<9) & (!found) ) & (y>=X[i]))
       {
            if  (X[i]==y)
                  found=true;
            else
                  i= i + 1;
        }
        if (found)
           cout << y <<" ditemukan pada index array ke-" << i;
        else
           cout << y  <<" tidak ada dalam Array tersebut":
    }


    Proses pencarian sekuensial data sudah terurut dengan sentitel

      Jika digunakan cara pencarian dengan sentinel (elemen yang dicari disisipkan di index setelah data terakhir), dan elemen yang dicari lebih besar dari data terakhir yang ada di Array sehingga data yang dicari sama dengan data sentinel maka dapat disimpulkan data tidak ditemukan

      Contoh Program SeqSearch_BelumUrut_Sentinel {Cara_1)

      /* SeqSearch_BelumUrut_Sentinel {Cara_1}
      diasumsikan Array X [1..nMax] sudah ada dan indeks ke 1..n berisi data yang sudah terurut, nilai yang dicari adalah Y dan hanya ada satu  */

      #include <iostream.h>
      typedef enum boolean {false=0, true=1};
      main()
      {
          int X[11]={10,20, 30, 40, 50, 60, 70, 80, 90, 100};
          int i,y;
          boolean found;
          cout << "nilai yang dicari = ";  cin >> y;
          X[10]=y;
          found=false;
          i=0;
          while ( (!found) & (X[i]<y) )
                  i= i + 1; //tidak ada pengecekan ditemukan atau tidak ditemukan
         if  (i>9)
                cout <<" tidak ada " << y << " dalam Array";
          else
             if (X[i]==y)
             cout << y  <<" tidak ada dalam Array pada indeks ke-": << i;
             else
               cout << "tidak ada " << y << "  dalam Array";
      }


      Contoh Program SeqSearch_BelumUrut_Sentinel {Cara_2}

      /* SeqSearch_BelumUrut_Sentinel {Cara_2}
      diasumsikan Array X [0..10] sudah ada dan indeks ke 0..9 berisi data yang belum terurut, nilai yang dicari adalah Y dan hanya ada satu  */

      #include <iostream.h>
      typedef enum boolean {false=0, true=1};
      main()
      {
          int X[11]={10,20, 30, 40, 50, 60, 70, 80, 90, 100};
          int i,y;
          boolean found;
          cout << "nilai yang dicari = ";  cin >> y;
          X[10]=y;
          found=false;
          i=0;

          while ( (!found) & (X[i]<y) )
         {  if (X[i]==y)
                  found=true;
             else
                  i= i + 1;
          }
         if  (i==10)
                cout <<" tidak ada " << y << " dalam Array";
          else
             if (found)
               cout << y  <<" tidak ada dalam Array pada indeks ke-": << i;
             else
               cout << "tidak ada " << y << "  dalam Array";
      }