Program Binary Search (String) Di C++

Berikut algoritma binary search serta penerapan di C++ :

1. Input seluruh data kedalam array
2. Input data yang dicari
3. Tentukan nilai kiri, kanan, dan tengah dengan rumus :

1. Kiri sama dengan nol
2. Kanan lebih kecil dari jumlah data
3. Tengah sama dengan hasil kanan dikurangi hasil kiri dibagi dua.

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

1. 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.
2. 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.
3. Tengah sama dengan kiri ditambah (kanan - kiri) dibagi dua.

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

Program

/* Program : Binary Search

    Karya   : blog-sharings.blogspot.com */

#include <iostream.h>

#include <conio.h>

#include <string.h>

main ()

{

    int jd,no,kiri,kanan,center;

    char data[20][50],cari[20];

   cout<<"\n\t\t *************************************** \n";

   cout<<"\t\t | \t\t\t\t       | \n";

   cout<<"\t\t | \t     Proses Pencarian \t       | \n";

   cout<<"\t\t | Menggunakan Algoritma Binary Search | \n";

   cout<<"\t\t | \t\t\t\t       | \n";

   cout<<"\t\t *************************************** \n\n\n";

    cout<<" Input Jumlah Data  : ";

    cin>>jd;

   cout<<endl;

    for (no=0;no<jd;no++)

    {

        cout<<" Input Data Ke-"<<(no+1)<<"    : ";

       cin>>data[no];

    }

   cout<<endl;

    cout<<" Input Nilai Dicari : ";

    cin>>cari;

    kiri=0;

    kanan=jd-1;

   center=(kanan-kiri)/2;

    while ((strcmp(data[center],cari)!=0) && (kiri>=0)&& (kanan<jd) && (kanan>=kiri))

    {

        if (strcmp (cari,data[center])>0)

       {

           kiri=center+1;

       }

       else if (strcmp (cari,data[center])<0)

       {

           kanan=center-1;

       }

       center=kiri+(kanan-kiri)/2;

    }

   cout<<endl;

    if (strcmp(data[center],cari)==0)

    {

        cout<<" Keterangan         : Data Ditemukan";

    }

    else

    {

        cout<<" Keterangan         : Data Tidak Ditemukan";

   }

    getch();

}

Read More

Program Binary Search Di C++

Pada postingan ini adalah penerapan dari Konsep Binary Search. Program C++ dibuat menggunakan aplikasi Borland C++ ver. 5.02 berdasarkan algoritma berikut :

1. Input seluruh data kedalam array
2. Input data yang dicari
3. Tentukan nilai kiri, kanan, dan tengah dengan rumus :

1. Kiri sama dengan nol
2. Kanan lebih kecil dari jumlah data
3. Tengah sama dengan hasil kanan dikurangi hasil kiri dibagi dua.

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

1. 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.
2. 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.
3. Tengah sama dengan kiri ditambah (kanan - kiri) dibagi dua.

5. 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.
   
   
   Program
   Binary Search.cpp
    /* Program : Binary Search
       Karya   : blog-sharings.blogspot.com */
   
   #include <iostream.h>
   #include <conio.h>
   
   main ()
   {
       int jd, cari,no, kiri,kanan,tengah,data[50];
   
      cout<<"\n\t\t *************************************** \n";
      cout<<"\t\t | \t\t\t\t       | \n";
      cout<<"\t\t | \t     Proses Pencarian \t       | \n";
      cout<<"\t\t | Menggunakan Algoritma Binary Search | \n";
      cout<<"\t\t | \t\t\t\t       | \n";
      cout<<"\t\t *************************************** \n\n\n";
   
      cout<<" Input Jumlah Data  : ";
      cin>>jd;
   
      cout<<endl;
       for (no=0;no<jd;no++)
       {
           cout<<" Input Data Ke-"<<(no+1)<<"    : ";
          cin>>data[no];
       }
   
      cout<<endl;
       cout<<" Input Nilai Dicari : ";
       cin>>cari;
   
       kiri=0;
       kanan=jd-1;
       tengah=(kanan-kiri)/2;
   
       while ((data[tengah]!=cari) && (kiri>=0)&& (kanan<jd) && (kanan>=kiri))
       {
           if (cari>data[tengah])
          {
              kiri=tengah+1;
          }
          else if (cari<data[tengah])
          {
              kanan=tengah-1;
          }
          tengah=kiri+(kanan-kiri)/2;
       }
   
      cout<<endl;
      if (data[tengah]==cari)
       {
           cout<<" Keterangan         : Data Ditemukan";
       }
       else
       {
           cout<<" Keterangan         : Data Tidak Ditemukan";
       }
   
       getch();
   }

Read More

Konsep 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), 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 dan Algoritma lebih rumit. Berikut ilustrasi pencarian menggunakan binary search dengan bantuan tabel. Misalkan kita mempunyai data sebagai berikut : {-5, -3, -1, 0, 1, 3, 5, 7}. Data yang kita cari adalah 5. 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 0 (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 3 (berwarna orange). Kemudian dibandingkan lagi dengan nilai yang dicari (5), 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 5 (berwarna orange). Kemudian dibandingkan lagi dengan nilai yang dicari (5), 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. Input data yang dicari
3. Tentukan nilai kiri, kanan, dan tengah dengan rumus :

1. Kiri sama dengan nol
2. Kanan lebih kecil dari jumlah data
3. Tengah sama dengan hasil kanan dikurangi hasil kiri dibagi dua.

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

1. 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.
2. 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.
3. Tengah sama dengan kiri ditambah (kanan - kiri) dibagi dua.

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

Untuk penerapan, binary search bisa dibuat dibeberapa bahasa pemograman. Berikut bahasa pemgoraman yang pernah dicoba untuk penerapan binary search :

• C++

Referensi :

kazwini13.wordpress.com

dharmaatmaja.wordpress.com

Read More

Program Sequensial Search (String) Di C++

Berikut program sequensial untuk mencari data berupa nama (string) berdasarkan algoritma:

1. Input seluruh data ke dalam array
2. Input data yang dicari
3. Tentukan nilai flag sama dengan nol.
4. Jika setiap nilai yang dicari sama dengan data yang terdapat dalam array, maka nilai flag akan bertambah satu.
5. Jika nilai flag tidak sama dengan nol, maka data ditemukan. Sedangkan jika nilai flag sama dengan nol, maka data tidak ditemukan. 
   

   Program

Sequensial Search (String).cpp

/* Program : Sequensial Search (String)

    Karya   : blog-sharings.blogspot.com */

#include <iostream.h>

#include <conio.h>

#include <string.h>

main()

{

    int no,jd,flag;

    char data[10][50],cari[10];

   cout<<"\n\t\t ******************************************* \n";

   cout<<"\t\t |  \t\t\t\t\t   | \n";

   cout<<"\t\t | \t\tProses Pencarian \t   | \n";

   cout<<"\t\t | Menggunakan Algoritma Sequensial Search | \n";

   cout<<"\t\t |  \t\t\t\t\t   | \n";

   cout<<"\t\t ******************************************* \n\n\n";

    cout<<" Input Jumlah Data  : ";

    cin>>jd;

    cout<<endl;

    for (no=0;no<jd;no++)

    {

        cout<<" Input Data Ke-"<<(no+1)<<"    : ";

        cin>>data[no];

    }

   cout<<endl;

    cout<<" Input Nilai Dicari : ";

    cin>>cari;

    flag=0;

    for(no=0;no<jd;no++)

    {

        if (strcmp (data[no],cari)==0)

       {

          flag++;

       }

    }

    cout<<endl;

    if (flag!=0)

    {

        cout<<" Keterangan         : Data Ditemukan"<<endl;

      cout<<" \t\t      Berjumlah "<<flag<<" Buah";

    }

    else

    {

        cout<<" Keterangan         : Data Tidak Ditemukan";

   }

    getch();

}

Read More

Program Sequensial Search Di C++

Postingan ini merupakan implementasi dari Konsep Sequensial Search. Program dibuat menggunakan aplikasi Borland C++ ver. 5.02 berdasarkan algoritma berikut :

1. Input seluruh data ke dalam array
2. Input data yang dicari
3. Tentukan nilai flag sama dengan nol.
4. Jika setiap nilai yang dicari sama dengan data yang terdapat dalam array, maka nilai flag akan bertambah satu.
5. Jika nilai flag tidak sama dengan nol, maka data ditemukan. Sedangkan jika nilai flag sama dengan nol, maka data tidak ditemukan.
   
   
   Program
   
   
   

   Sequensial Search.cpp

   /* Program : Sequensial Search
       Karya   : blog-sharings.blogspot.com */
   
   #include <iostream.h>
   #include <conio.h>
   
   main()
   {
       int no,jd,cari,flag,data[50];
   
      cout<<"\n\t\t ******************************************* \n";
      cout<<"\t\t |  \t\t\t\t\t   | \n";
      cout<<"\t\t | \t\tProses Pencarian \t   | \n";
      cout<<"\t\t | Menggunakan Algoritma Sequensial Search | \n";
      cout<<"\t\t |  \t\t\t\t\t   | \n";
      cout<<"\t\t ******************************************* \n\n\n";
   
       cout<<" Input Jumlah Data  : ";
       cin>>jd;
   
       cout<<endl;
   
       for (no=0;no<jd;no++)
       {
           cout<<" Input Data Ke-"<<no+1<<"    : ";
           cin>>data[no];
       }
   
      cout<<endl;
   
       cout<<" Input Nilai Dicari : ";
       cin>>cari;
   
       flag=0;
       for(no=0;no<jd;no++)
       {
           if (data[no]==cari)
           {
               flag++;
          }
       }
   
      cout<<endl;
   
       if (flag!=0)
       {
           cout<<" Keterangan         : Data Ditemukan"<<endl;
         cout<<" \t\t      Berjumlah "<<flag<<" Buah";
       }
       else
       {
           cout<<" Keterangan         : Data Tidak Ditemukan";
       }
   
       getch();
   }  
   

Read More

Konsep Sequensial Search

Metode Sequensial Search 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 sebelum melakukan pencarian. 

 

Kemungkinan terbaik (best case) dalam pencarian sequensial adalah jika data yang dicari terletak di indeks array terdepan (elemen array pertama) sehingga waktu yang dibutuhkan untuk pencarian data sangat pendek (minimal). Kemungkinan terburuk (worst case) adalah jika data yang dicari terletak di indeks array terakhir (elemen array terakhir) sehingga waktu yang dibutuhkan untuk pencarian data sangat lama (maksimal). 

 

Berikut ilustrasi langkah-langkah pencarian dengan menggunakan sequensial search dengan menggunakan tabel. Misalnya dalam suatu array dengan nilai {3,1,7,2,3,4} dan array dimulai dari 0, serta nilai yang dicari adalah nilai 3. Program akan mencari hingga akhir data. Jika didalam array terdapat nilai 3, maka variabel flag akan di beri nilai 1 dengan nilai awal (diinisialiasasi) dengan nilai 0. Berikut penjelasannya dalam bentuk tabel :

Hasil dari variabel flag ini akan menentukan apakah data ditemukan atau tidak. Jika nilai flag lebih dari 0, maka data ditemukan. Sebaliknya jika nilai flag sama dengan 0, maka data tidak ditemukan.

Untuk lebih jelasnya lagi perhatikan algoritma deskriptif pencarian sequensial.

1. Input seluruh data ke dalam array
2. Input data yang dicari
3. Tentukan nilai flag sama dengan nol.
4. Jika setiap nilai yang dicari sama dengan data yang terdapat dalam array, maka nilai flag akan bertambah satu.
5. Jika nilai flag tidak sama dengan nol, maka data ditemukan. Sedangkan jika nilai flag sama dengan nol, maka data tidak ditemukan.

Berbicara tentang penerapan dalam pemrograman, berikut penerapan pencarian sequensial pada beberapa bahasa pemrograman.

• C++
• PHP
• Pascal
• Perl
• Python
• Javascript

Referensi :

allaboutalgoritma.blogspot.com

Read More