Selasa, 30 Juni 2009

Binary Search

Metode Binary Search :

Jika kita mempunyai sebuah file dari record-record yang telah dijalankan,

kita dapat melanjutkan menghapuskan memory pemeriksaan yang diperlukan

untuk mendapatkan kembali sebuah record yang telah dipakai oleh suatu teknik

binary search.

Suatu binary search dibandingkan dengan kunci dari pencarian record dengan

record tengah dari sebuah file. Kemudian masing-masing pencarian record

yang telah ditempatkan atau setengah dari file yang telah dihilangkan dengan

pertimbangan yang lebih lanjut. Dalam kasus yang sebelumnya, proses pemban-

dingan dari record tengah dilanjutkan dalam record-record selanjutnya.

Jika kita harus menghilangkan bagian atas dari sebuah file termasuk

record yang telah dibandingkan berlawanan. Selanjutnya jika kita harus

menghilangkan bagian bawah dari sebuah file termasuk record yang telah

dibandingkan berlawanan. Dalam pengulangan proses dari pembandingan

berlawanan dari record tengah, kita akhirnya akan menempatkan record yang

kita inginkan atau menentukan bahwa itu tidak ada dalam file ketika tidak

ada record-record selanjutnya.

Algoritma Binary Search :

Terendah = 1.

Tertinggi = n.

While terendah <>

Tengah = (terendah + tertinggi) / 2.

if nilai kunci = nilai (tengah). Then data ditemukan.

Else if nilai kunci > nilai (tengah). Then terendah = tengah + 1.

Else tertinggi = tengah - 1.

end

end

end

Mari kita amati sebuah contoh dari suatu binary search yang telah disajikan terhadap suatu file dari record-record yang telah disusun secara urut. Dalam contoh ini, kita mencari record-record dengan kunci 39, dimana berindikasikan record yang terbaru yang telah dibandingkan berlawanan dari tanda kurung besar membatasi record yang masih dibawah pertimbangan.

Contoh :

Di bawah ini adalah kunci–kunci carilah kunci 39 dengan mengunakan algoritma Binary Search.

[13, 16, 18, 27, 28, 29, 38, 39, 53].

1 2 3 4 5 6 7 8 9

File ini dinamakan File Sequential (secara berurutan).

Cara penyelesaian.

Bila di cari kunci 39 maka ;

Bila terendah = 1, dan tertinggi = 9,

maka 1 + 9 = 10 , lalu 10 / 2 = 5.

1. Nomor urut 5, adalah kunci 28 , tapi 28 <>

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 5 , dan tertinggi = 9,

maka : 5 + 9 = 14

14 / 2 = 7.

2. Nomor urut 7 adalah 38 , tapi 38 <>

[13, 16, 18, 27, 28, 29, 38, 39, 53].

maka terendah = 8, dan tertinggi = 9, (karena mid + 1 jadi 7+1=8)

maka : 8 + 9 = 17

17 / 2 = 8,5 => 8,5 ≈ 8

3. Nomor urut 8 adalah kunci 39 , dimana kunci 39 = 39.

[13, 16, 18, 27, 28, 29, 38, 39, 53]

0 komentar:

Posting Komentar

Template Design by SkinCorner