SEARCHING BINARY DALAM C++

Pengertian Searching Binary

Pencarian (searching) merupakan proses pengelohan data untuk  menemukan nilai(data) tertentu di dalam sekumpulan data yang bertipe sama. Terdapat metode pencarian terurut yang lebih efisien yaitu metode pencarian biner(binary) atau pencarian bagi dua. Metode ini digunakan untuk kebutuhan pencarian dengan waktu yang cepat. Sebenarnya dalam kehidupan sehari-hari kita sering menerapkan algoritma ini. Misalnya untuk mencari kata tertentu dalam kamus, kita tidak membuka kamus tersebut dari haaman awal sampai akhir namun dengan membelah atau membagi halaman buku tersebut kemudian mencari kata yang kita cari.

Algoritma Searching Binary

Pertama, kita anggap bahwa data sudah terurut misalkan terurut menurun. Misalnya indeks kiri Ia dan indeks kanan Ib.Ia awalnya bernilai 0 dan Ib adalah N.

1. Bagi data menjadi 2 elemen pada elemen tengah.Elemen tengah adalah elemen dengan indeks k=(Ia+Ib) div 2.

2. Program akan memeriksa apakah l=[k]=X, jika L[k] =X, pencarian akan terhenti sebab X sudah ditemukan. Apabila tidak, maka program akan menentukan apakah akan melakukan pencarian pada larik kanan atau kiri. Jika L[k]<X maka pencarian akan dilakukan pada larik kiri, namun jika L[k]>X maka pencarian akan dilakukan pada larik kanan.

3.  Program akan mengulang langkah I sampai X atau Ia>Ib.

Ilustrasi pencarian bagi dua:

Misalnya larik L dengan delapan buah elemen yang sudah terurut menurun seperti berikut.

 

1. X=18 (data yang dicari)

    i=1 dan j=8

    k = (1+8) div 2 = 4

 

    L[4]=18

    Pencarian ditemukan

2. X=100

    i=1 dan j=8

    k = (1+8) div 2 = 4

    L[4]<100, maka pencarian akan dilanjutkan pada larik kiri dengan i=1 dan j=k-1=3

    k=(1+3) div 2 =2

   

      

    L[2] < 100, maka dilakukan pencarian pada larik kiri dengan i=1 dan j= k-1 =1

   

   L[1] <100, maka pencarian dilakukan dari bagian kiri dengan i=1 dan j=k-1= 0
   karena i>j, maka tidak ditemukan larik yang tersisa. proses dihentikan.

Contoh Program

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

using namespace std;

int main()
{
    int i=5;
    int j;

    int array[i]={1,2,3,4,5};
    int awal, tengah, akhir;

    cout<<"Enter a target to be found: ";cin>>j;

    awal = 0;
    akhir = 4;

    while(awal<=akhir)
    {
        tengah=(awal + akhir)/2;
        if(j>array[tengah])
        {
            awal= tengah+ 1;
        }
        else if (j<array[tengah])
        {
            akhir=tengah+1;
        }
        else
        {
            awal=akhir+1;
        }
    }
    if(j==array[tengah])
    {
        cout<<"Target Found"<< endl;
    }
    else
    {
        cout<<"Target not found"<<endl;
    }
    getch();
} 

Referensi

https://www.academia.edu/8572021/Modul_Struktur_Data_C_STMIK_AMIKOM_YOGYAKARTA
http://muhajaryama95.ilearning.me/?p=73

https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=2ahUKEwjUwYaVqe_hAhVEYKwKHaauD0QQFjABegQIBBAC&url=http%3A%2F%2Fdinus.ac.id%2Frepository%2Fdocs%2Fajar%2Fsearching.ppt&usg=AOvVaw2TStZWkVwpeT3aM9pl36Ij

 

Read More →

SEARCHING SEQUENTIAL DALAM C++

PENGERTIAN SEARCHING

Pencarian atau searching adalah suatu pekerjaan yang sering dikerjakan dalam kehidupan sehari-hari dengan tujuan untuk mengetahui apakah sesuatu yang dicari tersebut ada atau tidak ada. Proses perncarian dalam searching misalkan menemukan data tertentu di dalam sekumpulan data yang bertipe data sama atau tipe bentukan.

Data searching merupakan proses yang dibutuhkan dalam suatu pembangunan aplikasi. Banyak algoritma searching dapat dilakukan namun tidak semua berjalan dengan efisien. Misalkan untuk data yang sedikit mungkin perbedaan belum terlalu besar, namun jika terjadi pengembangan data bisa jadi itu disebut dengan big data. Big data adalah sekumpulan data yang sangat besar yang disimpan dalam sebuah database.

Ada beberapa algoritma pencarian yaitu:

a. Sequential searching

b. Binary searching

Pada kali ini, kita akan membahas tentang sequential searching yaitu algoritma dasar dari pencarian, dimana menggunakan data paling awal dan akhir dengan berurutan.

SEQUENTIAL SEARCHING

Sequential search adalah cara untuk pencarian data dalam array satu dimensi. data yang akan dicari nanti ditelusuri dalam semua elemen yang tersimpan dari data yang awal sampai data yang akhir. 

Contoh:

1. Data:

    Lia| Caca| Bily| Mia| Lisa| Andri | Deni

    Data yang dicari:

    Mia

    Compare data yang dicari:

    List [0] Lia

    List [1] Caca

    List [2] Bily

    List [3] Mia - Success! 

2. Data:

    Lia| Caca| Bily| Mia| Lisa

    Data yang dicari:

    Bobby

    Compare data yang dicari:

    List [0] Lia

    List [1] Caca

    List [2] Bily

    List [3] Mia

    List [4] Lisa- Not found!

Algotitma Sequential Searching

1. i <- 0
2. Ketemu <- False
3. Selama (tidak ketemu) dan (i<=N) maka program akan mengerjakanprogram no 4
4. Jika (Data[i]=x) maka  i adalah indeks data yang dicari ketemu <- true
5. Jika data belum ditemukan maka i<-i<+1

6. Apabila data tidak ada maka akan keluar pemberitahuan bahwa data yang dicari tidak ada

Contoh Program

#include <stdio.h>
#include <conio.h>

using namespace std;

int main(){
int data[8] = {8,10,6,-2,11,7,1,100};
int cari;
int flag=0;
printf("masukkan data yang ingin dicari = ");scanf("%d",&cari);
   for(int i=0;i<8;i++)
{
                if(data[i] == cari) flag=1;
}
if(flag==1) printf("Data ada!\n");
else printf("Data tidak ada!\n");
getch();
return 1;
}

Running:

 

 Dari program diatas:

1. Program menggunakan sebuah variabel flag yang berguna untuk mencari ada tidaknya data yang dicari didalam array.

2. Falag pertama berinisialisasi nilai 0.

3. Jika ditemukann maka flag akan bernilai 1, namun jika tidak maka flag akan bernilai tetap atau 0.

4. Semua elemen array akan dibandingkan satu persatu dengan data yang dicari atau yang diinputkan oleh pengguna. 

Reference

https://kelasinformatikaku.blogspot.com/2012/06/algoritma-searching-di-c_10.html
http://darasinta.blogspot.com/2010/12/algoritma-searching.html
http://unsri.ac.id/upload/arsip/pencarian.pdf
https://www.academia.edu/16000508/ANALISIS_ALGORITMA_SEQUENTIAL_SEARCH_DAN_BINARY_SEARCH_PADA_BIG_DATA
http://desy.lecturer.pens.ac.id/Logika%20Algoritma/TM_13%20-%20Searching.pdf

Read More →