Sebutkan kunci proses dari algoritma untuk Binary Search

March 10, 2014 by fithri selva

Pencarian bagidua atau pencarian biner adalah metode pencarian yang diterapkan pada sekumpulan data yang sudah terurut (terurut menaik atau terurut menurun). Data yang terurut syarat mutlak penerapan algoritma ini. Salah satu keuntungan data terurut adalah memudahkan pencarian, dalam hal ini pencarian bagidua.

Misalkan indeks kiri adalah Ia dan indeks kanan adalah Ib. Kondisi awal Ia=1 dan Ib = N. Langkah 1. Bagi dua elemen larik pada elemen tengah. Elemen tengah adalah elemen dengan indeks k = (Ia+Ib) div 2

(elemen tengah , L[k], membagi larik menjadi dua bagian, yaitu bagian kiri L[Ia..k-1] dan bagian kanan L[K+1..Ib])

Langkah 2. Periksa apakah L[k] = X. Jika L[k] = X, pencarian dihentikan sebab X sudah ditemukan. Tetapi, jika L[k] ≠ X, harus ditentukan apakah pencarian akan dilakukan di larik bagian kiri atau di bagian kanan. Jika L[k] < X, maka pencarian dilakukan pada bagian kiri. Sebaliknya, jika L[k] > X, pencarian dilakukan pada larik bagian kanan.

Langkah 3. Ulangi langkah 1 sampai X ditemukan atau Ia > Ib (ukuran larik sudah nol).

Contoh :
Diketehui sebuah senarai belum terurut dan bilangan yang akan dicari adalah 2 :

Penyelesaian :

1. Urutkan terlebih dahulu semua bilangan, boleh terurut menaik atau terurut menurun. Kali ini saya akan menggunakan terurut menaik sehingga diperoleh array sebagai berikut dan kemudian saya tambah dengan keterangan urutan di baris bawah.

2. Tentukan Indek atas (Ia) dan indek bawah (Ib). Ia adalah nilai indek terbesar dari array yaitu 10. Sedangkan Ib indek terkecik dari array yaitu 1. dan kita tetapkan bahwa saat ini ketemu=tidak ketemu. 3. Cek apakah saat ini ketemu != ketemu dan Ib < dari Ia? Jika iya maka buka elemen ke-k, dimana k adalah Ia+Ib/2 = 10+1/2= 5 (Biasanya pembulatan kebawah). 4. Sekarang periksa elemen ke-5 apakah sama dengan 2 (bilangan yang dicari)? Ternyata bukan, elemen ke-5 adalah 6.

5. Karena bukan maka periksa apakah nilai elemen ke-5 > dari 2?? Jika iya maka nilai Ia akan diubah menjadi k atau sama saja dengan Ia=k=5. Sehingga area yang dicari menjadi lebih sempit.

6. Cek apakah saat ini ketemu != ketemu dan Ib < dari Ia? Jika iya maka buka elemen ke-k, dimana k adalah Ia+Ib/2 = 1+5/2= 3. 7. periksa elemen ke-3 apakah sama dengan 2 (bilangan yang dicari)? Ternyata bukan, elemen ke-3 adalah 4.

8. Karena bukan maka periksa apakah nilai elemen ke-3 > dari 2?? Jika iya maka nilai Ia akan diubah menjadi  k atau sama saja dengan Ia=k=3.

9. Cek apakah saat ini ketemu != ketemu dan Ib < dari Ia? Jika iya maka buka elemen ke-k, dimana k adalah Ia+Ib/2 = 1+3/2= 2.
10. periksa elemen ke-2 apakah sama dengan 2 (bilangan yang dicari)? Ternyata benar. Jika benar ketemu =ketemu.
11. Cek apakah saat ini ketemu != ketemu dan Ib < dari Ia? tidak! ketemu=ketemu maka perlulangan berhenti.

Jika dilihat kembali dengan binary search elemen yang diperiksa hanya elemen ke 5, 3 dan 2. dengan tiga langkah elemen yang dicari langsung ketemu.

ANALISIS ALGORITMA BINARY SEARCH Metode Binary search Binary search merupakan salah satu algoritma untuk melalukan pencarian pada array yang sudah terurut. Jika kita tidak mengetahui informasi bagaimana integer dalam array, maka penggunaan binary search akan menjadi tidak efisien, kita harus melakukan sorting terlebih dahulu atau menggunakan metode lain yaitu linear search. Namun jika kita telah mengetahui integer dalam array terorganisasi baik secara menaik atau menurun, maka bisa dengan cepat menggunakan algoritma binary search. Adapun ide dasar binary search yaitu memulai pencarian dengan membagi dua ruang pencarian. Misalnya kita memiliki array A, dan kita ingin menemukan lokasi dari spesifik target integer K dalam array. Ada 3 kemungkinan kondisi pada binary search yaitu: 1. Jika data target K langsung di temukan, maka proses pembagian ruangan berhenti. Kemudian print out data elemen pada array. 2. Jika data target K < A[dle], maka pencarian dapat dibatasi hanya dengan melakukan pencarian pada sisi kiri array dari A[dle]. Seluruh elemen yang berada di sebelah kanan dapat di abaikan. 3. Jika data target K > A[dle], maka akan lebih cepat jika pencarian di batasi hanya pada bagian sebelah kanan saja. 4. Jika seluruh data telah di cari namun tidak ada, maka diberi nilai seperti -1. Dibawah ini merupakan salah satu version program binary search. Kamus Conts N : Type t=array[0 N] of integer val, left, right, : Integer Algoritma int binarysearch(list t[], int n, int val) { int left, right, ; } left = 0; right = n-1; while(left<=right) { =(left+right)/2; if (val<t[].key) right=-1; else if (val>t[].key) left=+1; else return ; /* found */ } return -1; /* not found */ Analisis dan Desain Algoritma (G651120381) 1

Analisis Kompleksitas Contoh data yang sudah terurut : Kasus 1 : cari = 13 Left = 0 Right = 7 Loop (1) : = (left +right) div 2 = (0 + 7) div 2 = 3 t [] = A [3] = 13, pada loop pertama data langsung ditemukan left right Output = 3 Target Kasus 2 : cari = 17 Left = 0 Right = 7 Loop (1) : = (left +right) div 2 = (0 + 7) div 2 = 3 t [] = A [3] = 13 < val = 17, data belum ditemukan, berarti left = + 1 = 3 + 1 = 4 left right Analisis dan Desain Algoritma (G651120381) 2

Loop (2) : = (left +right) div 2 = (4 + 7) div 2 = 5 t [] = A [5] = 18 > val = 17, data belum ditemukan, berarti right = - 1 = 5-1 = 4 left right Loop (3) : = (left +right) div 2 = (4 + 4) div 2 = 4 t [] = A [4] = 17 = val = 17, data ditemukan setelah loop ketiga Output = 4 Target Kasus 3 : cari = 2 Left = 0 Right = 7 Loop (1) : = (left + right) div 2 = (0 + 7) div 2 = 3 t [] = A [3] = 13 > val = 2, data belum ditemukan, berarti right = - 1 = 3-1 = 2 left right Loop (2) : = (left +right) div 2 = (0 + 2) div 2 =1 Analisis dan Desain Algoritma (G651120381) 3

t [] = A [1] = 3 > val = 2, data belum ditemukan, berarti right = - 1 = 1-1 = 0 left right Loop (3) : = (left +right) div 2 = (0 + 0) div 2 = 0 t [] = A [0] = 1 < val = 2, data belum ditemukan, left = +1 = 0 + 1 = 1 Loop (4) : = (left +right) div 2 = (1 + 0) div 2 = 0 Tidak bisa dijalankan karena 1 lebih dari 0 sehingga loop berhenti di loop ketiga. Sehingga data tidak dapat ditemukan Output = -1 Sekarang mari kita analisis metode binary search untuk menentukan kompleksitasnya. Ketika jumlah elemen dalam array 8: Ketika n=8, Binary Search dijalankan dengan mereduksi ukuran menjadi 4 Ketika n=4, Binary Search dijalankan dengan mereduksi ukuran menjadi 2 Ketika n=2, Binary Search dijalankan dengan mereduksi ukuran menjadi 1 Dapat kita lihat bahwa binary search dipanggil sebanyak tiga kali (3 elemen dalam array yang dieksekusi) untuk n = 8. Sehingga didapat 8 = 2 3 atau secara general kita katakan n = 2 k. ketika kita mengeksekusi x pencarian, while loop juga dieksekusi sebanyak x kali dan n di reduksi ukurannya menjadi Analisis dan Desain Algoritma (G651120381) 4

1. Pada contoh penerapan di atas, dapat disimpulkan jumlah maksimum total operasi yang dilakukan adalah sebanyak 3. Nilai dari k dapat dinotasikan menjadi 2 k = n sehingga k = log 2 n Jumlah operasi yang dilakukan untuk mencari k adalah sebanyak = 3 log n. pada kasus terburuk, yaitu kasus dimana k tidak terdapat dalam array adalah T(n) = log 2 n Misalnya jika kita memiliki array sebanyak 1024 elemen, kasus terburuk menghasilkan pembandingan array sebanyak log 2 1024 = 10 kali. Bandingkan dengan linear search yang pada kasus terburuknya melakukan pembandingan sebanyak 1024. Tentunya algoritma binary search menjadi lebih cepat. Namun jika data yang ada merupakan data yang tidak terurut maka akan jauh lebih cepat jika menggunakan linear search. Jika menggunakan binary search maka akan ada cost tambahan yaitu mengurutkan array terlebih dahulu. Algoritma binary search biasa di gunakan untuk database. Pada database tidak perlu ada algoritma sorting karena pada database sendiri sudah disediakan fungsi sorting baik untuk menaik atau menurun. Binary Search Tree Binary Tree ini memiliki sifat dimana semua left child harus lebih kecil dari pada right child dan parentnya. Semua right child juga harus lebih besar dari left child serta parentnya. Binary search tree dibuat untuk mengatasi kelemahan pada binary tree biasa, yaitu kesulitan dalam searching / pencarian node tertentu dalam binary tree. Algoritma Algorithm searchbst (root, targetkey) If (empty tree) return null *not found End if If (targetkey < root) return searchbst (left subtree, targetkey) else if (targetkey > root) return searchbst (right subtree, targetkey) else return root *found target end if end searchbst Analisis dan Desain Algoritma (G651120381) 5

Contoh Binary Search tree Proses pencarian sukses Search(7) 8 < 15 15 5 8 < 5 23 3 8 18 8 = 8 6 Data yang dicari berhasil ditemukan Proses pencarian gagal Search(9) 9 < 15 15 5 9 < 5 23 3 8 18 6 Data tidak ada Data yang dicari GAGAL ditemukan Analisis Kompleksitas Binary Search Tree Kelemahan yang sangat mendasar pada Binary search tree adalah elemen-elemen pada tree yang harus berurut. Binary Tree yang tidak balance dapat membuat seluruh operasi memiliki kompleksitas running time O(n) pada kondisi worst case. Sedangkan pada kondisi Analisis dan Desain Algoritma (G651120381) 6

Binary Tree yang balanced maka waktu rata-ratanya adalah log n. Proses pencarian pada tree sangat bergantung pada ketinggian suatu tree. Pada contoh kasus diatas ketinggian tree adalah 3. 15 5 23 h 3 8 18 6 Maksimum operasi perbandingan jika data gagal ditemukan adalah sebanyak 3 kali. Jika data yang dicari berada di root (Target=15), best casenya adalah 1 kali pembandingan. Daftar Pustaka Aslam & Fell.Analysis of Algorithms: Running Time. 2005. CSU 2000 discrete Structures Fall 2005. Analisis dan Desain Algoritma (G651120381) 7