Pada kesempatan kali
ini saya dari Jurusan Teknik Informatika akan menjelaskan Mengenai Pencarian
Bagi Dua (Binary Search).Sebelumnya kita mempelajari apa itu Pencarian Bagi Dua
(Binary Search) , mari kita flashback kembali apa itu Pencarian (Searching).
Pengertian
Pencarian(Searhing)
Pencarian atau Searching adalah proses dimana sebuah coding atau
algoritma digunakan untuk menemukan data atau nilai tertentu pada sekumpulan
data yang bertipe sama.
Setelah kita memahami apa itu pencarian(Searching) , sekarang saya akan
menjelaskan materi dari pencarian itu sendiri yaitu yang berjudul “Pencarian
Bagi Dua (Binary Search) “.Disini saya akan menjelaskan tentang pengertian ,
langkah mencari data dalam Pencarian Bagi Dua (Binary Search) , dan Contoh
Algoritma dari Pencarian Bagi Dua (Binary Search). Selamat Membaca :)
Pencarian Bagi Dua (Binary
Search)
1.
Pengertian Pencarian
Bagi Dua (Binary Search)
Pencarian Bagi Dua (Binary Search) adalah metode dari pencarian yang
menggunakan konsep membagi 2 jumlah elemen,larik atau array yang telah
ditentukan.Syarat utama dalam Pencarian Bagi Dua (Binary Search) ialah sekumpulan
data atau algoritma yang ingin dicari nanti sudah terurut, baik secara menaik
atau menurun.
Kelebihan menggunakan konsep Pencarian Bagi Dua (Binary Search) dalam
pencarian data yaitu waktu yang sangat cepat dalam pencarian.
2.
Langkah-langkah dalam
Mencari data Menggunakan Konsep Pencarian Bagi Dua (Binary Search)
Ø Berilah simbol untuk mempermudah dalam memproses data , seperti
sekumpulan data dikodekan menjadi n , larik dikodekan L , dan data yang akan
dicari dikodekan menjadi X.
Ø Sepakati bahwa nilai index awal atau kita kodekan menjadi a=0 dan index akhir
atau kita kodekan menjadi b=n-1.
Ø Tentukan apakah sekumpulan data terurut yang akan dicari bersifat menaik
atau menurun dengan cara membandingkan elemen kanan dan kiri
Ø Jika data elemen paling kiri L[0] > data elemen paling kanan L[n-1],
maka data terurut tersebut menurun.
Ø Jika data elemen paling kiri L[0] < data elemen paling kanan L[n-1],
maka data terurut tersebut menaik.
Ø Selanjutnya kita beri kode untuk index data tengah sebuah array tersebut
dengan variabel c , sehingga :
C = (a+b)div 2
Ø Dari rumus diatas,kita langsung mendapatkan data tengah nya.Lalu periksa
apakah L[c] = X , maka data yang dicari langsung didapat dari rumus C diatas.
Ø Tetapi jika L[c] < X maka pencarian data dilakukan dari sisi kanan
index c atau data tengah dengan menggunakan rumus C tersebut.Dan jika L[c]
>X maka pencarian data dilakukan dari sisi kiri index c atau data tengah
dengan menggunakan rumus C dimana dengan nilai b sama dengan nilai c dan
pencarian dilakukan sampai seterusnya hingga ketemu nilai X atau tidak sama
sekali.
(Note : Konsep ini
untuk data terurut menaik. Jika data terurut menurun maka hanya mengubah konsep
L[c]<X dari sisi kiri dan L[c]>X dari sisi kanan).
For Example :
Diberikan sebuah data terurut
sebanyak 8 elemen L[8] = {2,3,4,5,6,7,8,9}.Tentukanlah nilai X=3 di elemen
tersebut ?
Penyelesaian :
§ Tentukan apakah data terurut tersebut menaik atau menurun dengan
membaca L[0] dan L[n-1]
L[0] = 2
L[7] = 9
Karena
L[0] < L[7] maka data terurut tersebut menaik.
§ Misalkan index paling kanan a=0 dan index paling kiri b=7 maka index
tengahnya adalah :
C = (a+b)div 2 =
(0+7)div 2 = 3.
Dari
konsep index C didapat elemen tengah adalah 3 dengan L[3] = 5.
§ Karena data index tengah lebih besar dari nilai yang akan dicari (L[3]
>X ) maka pencarian data berikutnya dilakukan pada sisi kiri index C dengan
syarat nilai index C sama dengan nilai b, sehingga :
B = C = 3 , C =
(a+b)div 2 = (0+3)div 2 = 1.
Elemen
tengah menjadi 1 dengan L[1] = 3
§ Karena nilai data di elemen tengah sama dengan niali yang dicari atau X
maka pencarian berakhir.Data X ditemukan di index ke-1.
§ Selesai
Selamat Membaca :) Semoga Bermanfaat :)
