algoritma binary search

BINARY SEARCH

Metoda Pencarian Biner ( Binary Search) hanya bisa diterapkan jika data array sudah teruru. pengurutan Array bisa menggunakan jenis sorting descending atau asscending. Kelebihan dari Searching dengan metode Binary Sort adalah Untuk Pencarian data yang jumlahnya banyak, waktu pencarian relatif cepat. selain itu beban komputasi juga lebih kecil karena pencarian dilakukan dari depan, belakang, dan tengah. namun ada pula kekurangannya, yaitu data harus disorting dahulu dan Algoritma lebih rumit, tidak baik untuk data berangkai.

Algoritma dari Binary Sort

Proses yang terjadi pada pencarian dengan metode ini adalah sebagai berikut :
1.Membaca Array data
2.Apabila Array belum terurut maka array diurutkan terlebih dahulu.
3.Menentukan data yang akan dicari
4.Menentukan elemen tengah dari array
5.Jika nilai elemen tengah sama dengan data yang dicari, maka pencarian berhenti.
6.Jika elemen tengah tidak sama dengan data yang dicari maka :
a.Jika nilai elemen tengah > data yang dicari maka pencarian dilakukan pada setengah array pertama.
b.Jika nilai elemen tengah lebih kecil dari pada data yang dicari maka pencarian dilakukan pada setengah array berikutnya.


ILUSTRASI BINARY SEARCH

Misalkan saya mempunyai data sebagai berikut : 3,1,4,7,25,12,40,78,90,65. Maka data tersebut akan dicek, ternyata setelah dicek datanya belum terurut, maka dengan menggunakan metoda sorting yang sudah ada, maka kita bisa mengurut data tersebut, menjadi : 1,3,4,7,12,25,40,65,78,90
Setelah data tersebut diurutkan maka fungsi binary sort baru mulai bekerja mencari data. berikut cara dari Binary sort mencari data tersebut. misalnya data yang dicari adalah 65. maka pencariannya dijelaskan pada tabel berikut ini :





Pada data range diberi warna Hijau. Pencarian dimulai dari tengah,Kiri dan kanan. rumus untuk Posisi tengahnya adalah ( Posisi Akhir + Posisi Awal )/2. jadi Nilai tengah pada langkah pertama yaitu adalah 12 (berwarna merah) dan nilai targetnya adalah 65 (kuning). Karena nilai data yang dicari > dari data yang ditengah, maka pencarian menjadi dikanan dari nilai tengah. Setelah itu, Maka nilai 12 menjadi awal pencarian, selanjutnya dicari kembali nilai tengah pada range nilai 12 ke kanan sampai pada array dengan nilai 90. ternyata nilai tengahnya adalah 40. kemudian array dari nilai 40 dibandingkan dengan target, ternyata lebih besar, maka pencarian kembali mengarah ke kanan nilai tengah. Array dengan nilai 40 menjadi titik awal pencarian sekarang. dan sekarang nilai tengah nya adalah 65. maka dibandingkan dengan target ternyata sama, maka data sudah Ditemukan.




Referensi : http://dharmaatmaja.wordpress.com/tag/binary-search/

Tidak ada komentar:

Posting Komentar