Faisal_Asadi Al

PENCARIAN BAGI DUA (BINARY SEARCH)

Baiklah pada bagian ini saya akan coba menjelaskan atau mengeksplor ilmu yang saya dapatkan mengaenai pembahasan search atau pencarian tepatnya pencarian bagi dua (binary search) dalam mata kuliah ALGORITMA & PEMROGRAMAN. Sebelunya saya mau mengucapkan terimakasih kepada dosen algoritma dan pemrograman kami yaitu Mr.Affandes M.T, yang telah bersedia membimbing kami dalam mata kuliah ini sekaligus dosen yang paling exis menurut saya,, hahahah, dan enggak lupa juga terimakasih kepada teman-teman seperjuangan saya di TIF-2A’13, dan kepada best friend saya zahabi,adi,cinad,dedek,& ulfa, dan yang paling utama adalah kedua orang tua saya, yang selalu mendoakan saya agar selalu sukses, aminnnnn..... hehehe

Pada bagian ini saya akan membahas dari pengertian Binnary Search, tujuan dari binnary search, dan cara kerja sistem dalam binnary search, dan kelebihan yang dimiliki metdode pencarian bagi dua (Search Binary), dan lain sebaginya.

Pencarian Bagi Dua (Binary Search)

Ø Merupakan metode pencarian data terurut yang paling mangkus atau dengan kata lain adalah paling effecient.

Ø Pencarian bagi dua atau binnery search adalah, metode pencarian yang diterapkan pada sekumpulan data yang sudah terurut (maksudnya adalah, aqpakah data tersebut terurut dari nilai yang terkecil ke nilai yang terbersar, atau malah sebaliknya dari nilai terbesar kenilai yang terkecil).

Example :

Ket: data terurut dari nilai terkecil ke nilai yang terbesar

Ket: data terurut dari nilai terbesar ke nilai yang terkecil

Ø Data yang terurut adalah syarat mutlak dalam penerapan algoritma ini, dengan kata lain data yang ingin kita proses harus terurut terlebih dahulu. . . . paham? J J

Ø Salah satu keuntungan kita mengurutkan data terlebih dahulu adalah mempermudah kita dalam pencarian data.

Adapun tujuan kita memproses data dengan menggunakan pencarian bagi dua (Binnary search) adalah :

Memperkecil jumlah opersi pembandingan yang harus dilakukan antara data yang dicari dengan data yang terdapat dalam tabel, khususnya untuk jumlah data yang sangat banyak. . . . ., enggak kebayangkan kalau kita bandingkan data sampai ribuan data? Kayak enggak ada kerjaan yang lain aja? Hehehehe ......... J J J

Prinsip dasarnya adalah melakukan proses pembagian ruang pencarian secara berulang-ulang sampai data yang kita cari dapat kita temukan atau sampai data yang ada pada ruang tersebut tidak dapat dibagi lagi (berarti ada kemungkinan data yang kita cari tidak dapat ditemukan).

v Langkah-langkah pencarian data dalam Binnary Search

Langkah 1: terlebih dahulu anda hurus membagi dua larik yang telah tersedia, yaitu larik kiri dan laarik kanan, dimana diantara larik kiri dan larik kanan terdapaengan elemen tengat koofesien elemen tengah (K) dimana rumus untuk mencari k = (i +j ) div 2, dengan elemen tengah L[K].
larik bagian kiri L [i sampai j], dan pada larik kanan L[K+1 sampai j].

Langkah 2 : langkah selanjutnya adalah anda harus periksa apakah elemen tengah L[K] sama dengan X ( L[K] = X ) , jika sudah sama maka pencarian data sudah selesai, tetapi jika data belum ditemukan maka anda harus putuskan kembali apakah mencari dilarik kanan atau dilarik kiri, tetapi terlebih dahulu anda harus melihat data yang dicari terlebih dahuku, dengan permisalan L[K]' (elemen tengah aksen), selanjutnya jika elemen tengah lebih kecil dari pada data yang dicari ( L[K] < x) maka anda harus melakukan pencarian data dilarik sebelah kiri, dan begitu juga sebaliknya jika elemen tengah atau K lebih besar darai pada data yang dicarai ( L[K] > x), maka anda harus putuskan pencarian dilakukan sebelah kanan.

Langkah 3 :langkah selanjutnya adalah anda harus melakukan dan mengulangi langkah pertama sehingga data yang dicari (x) ditemukan dalam larik atau elemen awal (i) lebih besar dari pada elemen akhir (j) atau dengan kata lain ukuran larik sudah habis nol (0) !

v Example pencarian data dalam larik L

Sedikit illustrasi dalam pencarian data dalam larik dengan menggunakan
“binnary search”, : seandainya terdapat data dalam bentuk larik L dengan delapan (8) buah elemen, yang datanya sudah diurutkan mulai dari yang terbesar ke yang terkecil, seperti dibawah ini :

(A) Misalkan elemen yang dicari adalah x = 18.

Langkah 1:

Dari data pada larik diatas, kita bisa melihat bahwa i = 1 dan j = 8

Jadi untuk mencari indeks elemen tengahnya, kta masukkan kedalam rumus yang ada pada langkah 1,

yaitu : elemen tengah (K) adalah elmen awal (i) di jumlahkan dengan elemen akhir (j) dibagi 2
K = ( i + j ) div 2

maka : K = ( 1 + 8 ) div 2 = 4 (elemen yang diarsir)

(B) Misalkan elemen yang dicari adalah x = 16.

Langkah 1 :

I = 1 dan j = 8

Indeks elemen tengah k = ( 1+ 8 ) div 2 = 4 (elemen yang diarsir)

Langkah 2 :

Bandingkan kembali apakah L [4] = 16? Pasti jawaban anda Tidak!, maka langkah selanjutnya anda harus berfikir untuk memutuskan apakah pencarian dilakukan disebelah kanan, atau disebelah kiri.

Selanjutnya anda harus membandingkan apakah L [4] > 16? , maka lihat larik L [4] (elemen yang diarsir yaitu 18), maka sudah pasti L [4] > 16 atau (18>16) ? J J , maka langkah selanjutnya anda harus melakukan pencarian pada larik bagian kanan, dengan i = k+1 = 5 ( K = indeks pada nilai tengah pada tabel yaitu = 4 ), dan j = 8 (tetap).

Ket = elemen yang terdapat pada larik kanan

Langkah selanjtnya (anggap langkah 1 aksen):

Dari data pada tabel diatas anda dapat melihat bahwa i = 5 dan j = 8 , maka indeks elemen tenganya atau K= (5+8) div 2 = 6 (elemen yang diarsir pada tabel dibawah ini )

Ket : ( pada tabel diatas tabel tersebutkan berada dalam larik kanan, dan pada larik kanan ini, elemennya dibagi lagi menjadi dua bagian lagi yaitu kanan’ (kanan aksen) dan kiri ‘ (kiri aksen) seperti tabel yang diatas ).

Langkah selanjutnya (anggap langkah 2 aksen):

Bandingkan kembali (elemen yang diarsir) L [6] = 16? Maka pasinya tidak kerena elemen yang terdapat pada L [6] adalah 13, maka langkah anda selanjutnya adalah anda harus memutuskan apakah pencarian dilakukan disebelah kanan atau disebelah kiri.

Bandingkan kembali nilai masing-masing elemen apakah L [6] > 16? Maka jawabnya pasti tidak! karena elemen yang terdapat pada L[6] = 13 (elemen yang diarsir).

Maka lakukan pencarian pada larik bagian kiri dengan i =5(tetap) dan j = k-1 = 5

Jadi seperti ini dech. . . . . J J

Langkah selanjutnya (anggap langkah 1 double aksen heheh J) :

I = 5 dan j = 5

Maka indeks tengahnya atau K = (5+5) div 2 = 5 (elemen yang di arsir atau elemen dia sendiri, kan Cuma tinggal 1 elemen?)

(C) Misalkan elemen yang dicari adalah x = 100

Langkah 1 :

I = 1 dan i = 8

Indeks elemen tengah k = (1 + 8) div 2 = 4 (elemen yang diarsir)

Langkah 2:

bandingkan: L[4] = 100? Tidak! Harus diputuskan apakah pencarianakan dilakukan di bagian kiri atau di bagian kanan dengan pemeriksaansebagai berikut:

bandingkan: L[4] > 100? pastinya, Tidak! Lakukan pencarian pada larik

bagian kiri dengan i = 1 (tetap) dan j = k – 1 = 3

Langkah 1' (anggap langkah 1 aksen) :

i = 1 dan j = 3

Indeks elemen tengah k = (1 + 3) div 2 = 2 (elemen yang diarsir)

Langkah 2' (anggap langkah 2 aksen) :

bandingkan: L[2] = 100? Tidak! Harus diputuskan apakah

pencarian akan dilakukan di bagian kiri atau dibagian kanandengan pemeriksaan sebagai berikut:

bandingkan: L[2] > 100? Tidak! Lakukan pencarian pada larik

bagian kiri dengan i = 1 dan j = k – 1 = 1

Langkah 1" (anggap langkah 2 double aksen) :

i = 1 dan j = 1

Indeks elemen tengah k = (1 + 1) div 2 = 1 (elemen yang diarsir)

Berikut adalah algoritma pencarian bagi dua (Binary Search)

(A) : prosedure binary serach

(B) : Fungsi binary search

Dan yang terakhir adalah. . . . . . . .

Pencarian bagi dua (Binary Search ) dalam JAVA

Berikut ini adalah program pencarian bagi dua (Binary Search) dengan asumsi data yang diinputkan harus terlebih dahulu.

Ø Coding dalam java

package PRAKTIKUM;

public class pertemuan5

{

// property

private int[] data;

// konstruktor

public pertemuan5 (int n )

{

this.data = new int [n];

}

// fungsi set data

public void SetData(int index, int value )

{

if(index>=0 && index< this.data.length){

this.data[index] = value;

}

// public pencarian beruntun

public int cari (int x)

{

for(int a=0; a<this.data.length; a++){

if(this.data[a] == x){

return a;

}

return -1;

}

public static void main(String[]D)

{

// buat objek

pertemuan5 ch = new pertemuan5 (5);

// masukkan data

ch.SetData(0,15);

ch.SetData(1,21);

ch.SetData(2,32);

ch.SetData(3,56);

ch.SetData(4,98);

//cari data 27

System.out.println(" Data 21 ada di index ke "+ch.cari(21));

System.out.println(" Data 56 ada di index ke "+ch.cari(56));

System.out.println(" Data 15 ada di index ke "+ch.cari(15));

}

Ø Hasil outputnya . . . .

Data 21 ada di index ke 1

Data 56 ada di index ke 3

Data 15 ada di index ke 0

Pencarian bagi dua (Binary Search) dalam java, dengan menggunakan class Scanner Input .

Ø Codingnya Java

package PRAKTIKUM;

import java.util.Scanner;

public class BinSearch

{

// Property

private int [] data;

// Konstruktor

public BinSearch (int n)

{

this.data = new int [n];

}

// Fungsi Set Data

public void SetData (int index, int value)

{

if (index >= 0 && index<this.data.length){

this.data [index] = value;

}

// Fungsi Pencarian Bagi Dua

public int Cari(int x)

{

int i = 0;

int j = this.data.length-1;

return CariBagiDua (x,i,j);

}

// Fungsi Rekursif Cari Bagi Dua (Binary Search)

private int CariBagiDua(int x, int i, int j)

{

// Cek Jarak i ke j

if ((j-i) >= 0 ){

// Tentukan Titik Elemen Tengah (K)

int k = (j+i)/2;

//Cek

if (x == this.data[k]){

return k;

}else if(x < this.data[k]){

return CariBagiDua (x,i,k-1);

}else {

return CariBagiDua(x,k+1,j);

}

}else {

return -1;

}

public static void main(String[]cinta_KIMIA){

// Buat Scanner

Scanner inp = new Scanner(System.in);

// Tanya Jumlah Data

System.out.print("Masukkan Jumlah Data = ");

int n = inp.nextInt();

// Buat Objek

BinSearch bs1 = new BinSearch (n);

// Masukkan Data

System.out.println(" Data yang dimasukkan harus berurut dari Kecil Ke Besar! ");

for(int a=0; a<n; a++){

System.out.print(" Data ke "+a+ " = ");

bs1.SetData(a, inp.nextInt());

}

// Tanya angka yang dicari ?

System.out.print("Nilai Yang Dicari ? ");

int x = inp.nextInt();

// Hasil

System.out.print(" Data "+x+ " ada di Index Ke : "+bs1.Cari(x));

}

Ø Hasil outputnya . . . .

Masukkan Jumlah Data = 7

Data yang dimasukkan harus berurut dari Kecil Ke Besar!

Data ke 0 = 1

Data ke 1 = 2

Data ke 2 = 3

Data ke 3 = 4

Data ke 4 = 5

Data ke 5 = 6

Data ke 6 = 7

Nilai Yang Dicari ? 7

Data 7 ada di Index Ke : 6

Berikut inioutput atau hasil, permisalan jika data yang kita cari tidak ada pada data yang kita inputkan, seperti yang dijelaskan pada pembahasan diatas (misalkan data yang dicari adalah x =100)

Masukkan Jumlah Data = 8

Data yang dimasukkan harus berurut dari Kecil Ke Besar!

Data ke 0 = 7

Data ke 1 = 10

Data ke 2 = 16

Data ke 3 = 18

Data ke 4 = 21

Data ke 5 = 76

Data ke 6 = 81

Data ke 7 = 89

Nilai Yang Dicari ? 100

Data 100 ada di Index Ke : -1