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