Algoritma Binary Search

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

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

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]

Contoh 2

Ada 2000 kunci Mahasiswa AKAKOM dengana mengunakan Algoritma Binary Search. Carilah kunci 1345

Cara penyelesaian.

1. pergi ke tengah yaitu ; record dengan kunci 1000.
2. pergi ke record tengah pada separuh bagian ke-dua yaitu ; record sementara (1001+2000)/2 ketemu 1500, maka Record yang di cari ada diantara 1001- 1500.
3. pergi ke bagian tengah antara (1001+1499)/2, yaitu ; record 1250. Record yang dicari 1345 > 1250 berarti ada di antara 1250 - 1499.
4. pergi ke bagian tengah antara (1251+1499)/2 , yaitu ; 1375. Record yang di cari 1345 < 1375 , berarti ada di antara 1251 – 1274.
5. pergi ke bagian tengah antara (1251+1374)/2 atau 1312,5. Record yang di cari 1345 > 1312 , berarti ada di antara 1313 – 1374.
6. pergi ke-bagian tengah antara (1313+1374)/2 atau 1343,5. Record yang di cari 1345 > 1343, berarti ada di antara 1344 –1374.
7. pergi ke-bagian tengah antara (1344+1374)/2 atau 1359. Record yang di cari 1345 < 1359, berarti ada di antara 1334 – 1358.
8. pergi ke-bagian tengah antara (1344+1358)/2 atau 1351. Record yang di cari 1345 < 1351, berarti ada di antara 1344 – 1350.
9. pergi ke-bagian tengah antara (1344+1350)/2, atau 1347. Record yang di cari 1345 < 1347, berarti ada di antara 1344 – 1346.
10. pergi ke bagian tengah antara (1344+1346)/2, atau 1345. Record yang di cari1345 = 1345, ketemu.

Contoh 3

Dari data berikut gunakanlah metode binary search

Cari nomer kunci dari 232 , sedangkan jumlah seluruh mahasiswa sebanyak 700 orang.

Pembahasaan :

(1 + 700)/2 = 350

angka 350 lebih besar dari 232, maka kita harus mencarinya kembali.

(1+ 349)/2 = 175

angka 175 lebih kecil dari 232, maka kita akan mencari kembali

(176 + 349)/2 = 262

angka 362 lebih besar dari 232, maka kita akan melakukan pencarian lagi.

(176 + 261)/2 = 218

angka 218 lebih kecil dari 232 maka dicari lagi

(219 + 261)/2 = 240

angka 240 lebih besar dari 232, maka akan dicari lagi

(219 + 239)/2 = 229

angka 229 lebih kecil dari 232, maka akan dicari lagi

(230 + 239)/2 = 234

angka 234 lebih besar dari 232, maka akan dicari lagi

(230 + 233)/2 = 231

angka 231 lebih kecil dari 232, maka

(232 + 233)/2 = 232

sudah ditemukan

contoh 4

Di bawah ini adalah kunci–kunci carilah kunci 17 dan 39 dengan mengunakan algorithm Binary Search.

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

Jawab :

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 = 6, dan tertinggi = 9

maka 6 + 9 = 15 lalu 15 / 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,

maka 8 + 9 = 17, lalu 17 / 2 = 8.

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

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

Contoh 5

Dari daftar kunci berikut

2,5,11,12,14,19,30,32,41,42,47,49,51,52

Dicari suatu kunci 12 dan 42, tentukan pencarian tersebut dengan metode binary search

Cara penyelesaian.

Jika kita hendak mencari suatu kunci dari daftar berikut maka terlebih dahulu kita harus mengetahui daftar tertinggi dan daftar terendah jadi langkah pertama yang harus di ambil, yaitu :

1· mencari kunci dari angka 12 maka :

nilai terendah = 1 dan nilai tertinggi = 14

maka 1 + 14 = 15, lalu 15/2 = 7,5

2· karena nomer urut 7 adalah 30, maka 30 > 12

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka didapat nilai terendah = 1, dan nilai tertinggi adalah = 7

sehingga didapat : 1 + 6 = 7, lalu 7 / 2 = 3.

3· karena nomer urut dari nomer 3 adalah 11, maka 11 < 12

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka didapat nilai terendah = 4, dan nilai tertinggi adalah = 6

sehingga didapat : 4 + 6 = 10, lalu 10 / 2 = 5.

4· karena nomer urut dari nomer 5 adalah 14, maka 14 > 12

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka didapat nilai terendah = 4, dan nilai tertinggi adalah = 4

sehingga didapat : 4 + 4 = 8, lalu 8 / 2 = 4.

nomer 4 adalah kunci dari nomer 12, dimana kunci 12 = 12. ketemu

Untuk mencari kunci nomer 42 dengan methode Binary Search, maka :

1. dari daftar dibawah ini dapat kita lihat bahwa :

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

didapat nilai terendah = 1, dan nilai tertinggi = 14

hingga di dapat : 1 + 14 = 15, lalu 15 / 2 = 7,5

2. karena nomer urut 7 adalah 30, dan 30 < 42

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka di dapat nilai terendah = 8, dan nilai tertinggi = 14

jadi 8 + 14 =22, lalu 22/2 =11

3. karena nomer urut 11 adalah 47, dan 47 > 42

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka di dapat nilai terendah = 8, dan nilai tertinggi = 10

jadi 8 + 10 =18, lalu 18/2 =9

4. karena nomer urut 9 adalah 41, dan 41 < 42

[2, 5, 11, 12, 14, 19, 30, 32, 41, 42, 47, 49, 51, 52,]

maka di dapat nilai terendah = 10, dan nilai tertinggi = 10

jadi 10 + 10 =20, lalu 20/2 =10

nomer 10 adalah kunci dari nomer 42, dimana kunci 42 = 42, ketemu