algoritma 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 pembandingan 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.

Algorithm 2.1

Binary Search.

Terendah = 1.

Tertinggi = n.

While terendah < tertinggi do.

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 1

Di bawah ini adalah kunci–kunci carilah kunci 39 dengan mengunakan algorithm 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 < 39,

[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 < 39,

[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

Note: kl mengambil kebawah, haruskonsisten untuk jawaban selanjutnya jika ada kasus yg sama juga harus kebawah

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

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

referensi : http://blog.uad.ac.id/afandi/2008/11/06/binary-search/

algoritma divide dan conquer

adalah varian dari beberapa strategi pemrograman topdown,
tetapi keistimewaannya adalah membuat sub-sub problem dari problem yang
besar, oleh karena itu strategi ini ditunjukkan secara berulang-ulang (recursively),didalam menerapkan algoritma yang sama dalam sub-sub problem seperti yang diterapkan pada masalah aslinya (original problem). Sebagaimana prinsip dasar algoritma perulangan dibutuhkan sebuah kondisi untuk mengakhiri perulangan tersebut. Biasanya untuk mengecek apakah problem sudah cukup kecil untuk diselesaikan dengan metode secara langsung. Mungkin dari segi ilustrasi kita, bahwa proses-proses pada komputer paralel tentunya memiliki proses/problem/job yang cukup kompleks sehingga harus dipecah-pecah menjadi sub-sub problem. Selain dibutuhkan sebuah “kondisi”, juga diperlukan “fase divide” untuk membagi/memecah problem menjadi sub-sub problem yang lebih kecil, dan “fase combine“ untuk menggabungkan kembali solusi dari sub-sub problem kedalam solusi dari problem awalnya. Berikut pseudocode dari strategi divide and conquer

function d and c (p)
if basecase (p)
then
return solve (p)
else
(p1, : : :, pn) = divide (p)
return combine (d and c (p1), : : :, d and c (pn))
endif
Pseudocode untuk model algoritma n-way divide and conquer Pseudocode diatas adalah sebagai acuan dari strategi divide and conquer, tetapi dalam implementasinya ada beberapa diferensiasi dari bentuk diatas yang akan digunakan. Sebelum masuk ke pokok pemrograman dengan “Divide and Conquer strategy/algorithm”, ada 4 hal penting yang harus dipahami dalam strategi ini : branching factor, balance, data dependence of divide function dan sequentiality.

Branching Factor
Branching factor dalam algoritma divide and conquer adalah jumlah dari
subproblem yang akan dibagi dari sebuah problem awal. Ini adalah langkah
nyata dari algoritma divide and conquer, didalam proses pembagian yang
sebenarnya, jumlah dari branching factor harus 2 atau lebih, karena jika tidak
problem tidak bisa dibagi. Banyak jenis algoritma ini termasuk pula algoritma
komputasi geometric yang memiliki branching factor berjumlah 2.

Balance
Sebuah algoritma divide and conquer dikatakan balance jika problem awal dibagi
menjadi sub-sub problem dengan ukuran yang sama. Yang artinya jumlah dari
keseluruhan ukuran subproblem sama dengan ukuran problem awal (initial
problem). Algoritma Mergesort dan binary tree, dan sama halnya dengan
algoritma reduksi & prefix sum adalah beberapa contoh algoritma divide and
conquer yang seimbang (balance).

Data Dependence of Divide Function
Algoritma divide and conquer memiliki sebuah fungsi pembagian terhadap data
yang memiliki ketergantungan, artinya jika ukuran relatif dari sebuah
subproblem tergantung pada proses input datanya. Ini adalah salah satu ciri dari
algoritma yang tidak seimbang, salah satu contohnya adalah algoritma quicksort
yang akan membagi subproblem dengan fungsi data-dependent divide.

Control Parallelism or Sequentiality
Algoritma divide and conquer dikatakan berurutan (sequential) jika subproblem
dieksekusi sesuai dengan perintah program. Paralelisasi dari algoritma divide
and conquer yang terurut pertama kali didefinisikan oleh Mou’s Divacon[Mou90],
yang terjadi ketika hasil dari salah satu sub-eksekusi diperlukan oleh subeksekusi
yang lain. Dalam kasus ini hasil dari subtree pertama diberikan
(passing) kepada proses komputasi subtree kedua, supaya hasil akhir tersebut
bisa digunakan sebagai nilai awalnya, tetapi sekarang ini contoh diatas tidak
dapat dijadikan ilustrasi lagi karena teknologi komputer paralel yang semakin
canggih dan kompleks.

Contoh Penerapan Pada Binary Search
Temukan sebuah elemen atau bilangan pada array yang telah tersortir :
1. Divide : cek elemen tengah
2. Conquer : secara rekursif, cari disebuah subarray
3. Combine : trivial
Kasus :
Temukan bilangan 9 pada deret 3, 5, 7, 8, 9, 12, 15
Array awal

Temukan nilai tengah

Abaikan Subarray yang kurang dari 8

Temukan nilai tengah

Abaikan subarray yang lebih dari 12

Karena elemen tinggal satu, maka elemen tersebut adalah elemen yang dicari


Kesimpulan :
Algoritma divide and conquer sudah lama diperkenalkan sebagai sumber dari
pengendalian proses parallel, karena masalah-masalah yang terjadi dapat diatasi
secara independent. Banyak arsitektur dan bahasa pemrograman parallel
mendesain implementasinya (aplikasi) dengan struktur dasar dari algoritma
divide and conquer.
Divide and Conquer secara umum terbagi dalam tiga fase, divide yakni membagi
masalah kedalam sub-sub masalah yang lebih kecil, conquer yakni
menyelesaikan sub-sub masalah secara rekursif, dan combine menggabungkan
hasil dari penyelesian sub-sub masalah menjadi penyelesaian yang dikehendaki
Terdapat empat hal pada strategi “divide and conquer” : branching factor,
balance, data dependence of divide function dan sequentiality.

referensi :
http://www.informatika.org/.../Algoritma%20Divide%20and%20Conquer%20(lanjutan).ppt