Binary Search C++

Binary Search C++

Binary Search merupakan metode pencarian dimana data harus "diurutkan" terlebih dahulu sebelum dilakukan proses pencarian. Pada metode pencarian ini, data "dibagi" menjadi dua bagian untuk setiap tahap pencarian.

Penjelasan : 

Dalam pencarian Binary. kita harus memiliki data "Array" yang urut. Dalam pencarian nya kita kita membagi tabel array menjadi 2.

Misal Kita akan mencari Data 77. 

if array = 77 ? 

Tabel Array yang sudah kita urutkan kita bagi menjadi 2 Left Part dan Right Part. Lalu di cari apakah Data yang "di samping pembagi" adalah 77 ?

 

Jika True Maka Pencarian Selesai, jika FALSE maka "Left Part" akan di hilangkan.  

 

Setelah "Left Part" di hilangkan, maka Array hanya tinggal 3 Index. Lalu mulai lagi mencari titik tengah lagi dari Array yang tersisa.

 

'

Data di atas memiliki Top = 4 dan Bottom = 6. Lalu mencari "titik tengah" lagi dari data yang ada dan melihat apakah data "titik tengah" adalah data yang di cari ?

Jika Data nya TRUE, maka Pencarian Telah Selesai di lakukan.

Psudocode :

Start

    data[]=1,2,3,4,5

    search = 3

    first = 0, last = 4

    middle = (first+last)/2

     while first<=last

     do

          if data[middle] < search

       first = middle + 1

        else if data[middle] == search

       output found on index [middle]

       break

        else

           last = middle – 1

        end if

     middle = (first+last)/2

     end while

End

Code : 

#include <iostream>

using namespace std;

main(){
    int data[7]={1,2,3,4,5,6,7};
    int search;
    int first = 0, last = 6, j=0;
    int middle = (first+last)/2;
   
    cout <<"Masukkan Angka yang ingin di cari = ";cin>>search;
   
    while (first <= last) {
        if (data[middle]<search)
        {
            first = middle + 1;
        }
        else if (data[middle] == search)
        {
            cout <<"Data ditemukan Di Index "<<middle;
            j=1;
            break;
        }
        else
        {
            last = middle - 1;
        }
        middle = (first+last)/2;
    }
    if (j==0){
        cout <<"Data Tidak Di temukan";
    }
}

Tweet

Postingan terkait:

— Senin, 15 April 2019 — Add Comment