Algoritma Binary Search

Algoritma Pencarian Biner (Binary Search) Penerapan terbanyak dari pencarian biner adalah untuk mencari sebuah nilai tertentu dalam sebuah list terurut. Jika dibayangkan, pencarian biner dapat dilihat sebagai sebuah permainan tebak-tebakan, kita menebak sebuah bilangan, atau nomor tempat, dari daftar (list) nilai. Pencarian diawali dengan memeriksa nilai yang ada pada posisi tengah list; oleh karena nilai-nilainya terurut, kita mengetahui apakah nilai terletak sebelum atau sesudah nilai yang di tengah tersebut, dan pencarian selanjutnya dilakukan terhadap setengah bagian dengan cara yang sama.

ini adalah pseudocode sederhana yang menentukan indeks (posisi) dari nilai yang diberikan dalam sebuah list berurut, a berada antara left dan right : Karena pemanggilan fungsi di samping adalah rekursif ekor, fungsi tersebut dapat dituliskan sebagai sebuah pengulangan (loop), hasilnya adalah algoritma in-place: Pada kedua kasus, algoritma akan berakhir karena paa setiap pemanggilan rekursif atau pengulangan, jangkauan indeks right dikurang left akan selalu mengecil, dan akhirnya pasti akan menjadi negatif.

Pencarian biner adalah sebuah algoritma logaritmik dan bekerja dalam waktu O(log n). Secara khusus, 1 + log2N pengulangan yang diperlukan untuk menghasilkan jawaban. Hal ini dianggap lebih cepat dibandingkan sebuah pencarian linear. Pencarian biner dapat diimplementasikan dengan rekursi atau iterasi, seperti yang terlihat di atas, walaupun pada kebanyakan bahasa pemrograman akan lebih elegan bila dinyatakan secara rekursif. Pada intinya, algoritma ini menggunakan prinsip divide and conquer, dimana sebuah masalah atau tujuan diselesaikan dengan cara mempartisi masalah menjadi bagian yang lebih kecil. Algoritma ini membagi sebuah tabel menjadi dua dan memproses satu bagian dari tabel itu saja.

Algoritma ini bekerja dengan cara memilih record dengan indeks tengah dari tabel dan membandingkannya dengan record yang hendak dicari. Jika record tersebut lebih rendah atau lebih tinggi, maka tabel tersebut dibagi dua dan bagian tabel yang bersesuaian akan diproses kembali secara rekursif.

Algoritma Kamus Const N : integer = 8 { misalkan jumlah elemen array maksimum = 8 } Type A = array [ 1 ..... N ] of integer Cari, BatasAtas, BatasBawah, Tengah : Integer Ketemu : boolean ALGORITMA Input (cari) { meminta nilai data yang akan dicari} 1 { indeks array dimulai dari 1 }¬BatasAtas N¬BatasBawah False¬Ketemu While (BatasAtas < BatasBawah) and (not ketemu) do (BatasAtas + BatasBawah) div 2¬Tengah If A [Tengah] = cari then true¬Ketemu Else If ( A [Tengah] < cari ) then { cari di bagian kanan } Tengah + 1¬BatasAtas Else Tengah – 1 {¬BatasBawah cari di bagian kiri } Endif Endif EndWhile If (ketemu) then Output ( ‘Data berada di index nomor’, Tengah ) Else Output ( ‘Data tidak ditemukan’ ) Endif Kompleksitas Waktu

Kompleksitas waktu terbaik algoritma ini adalah 1, sedangkan kompleksitas waktu terburuknya 2log n. Kompleksitas waktu terburuk ini dicapai pada kasus dimana record tidak ditemukan dalam tabel. Pada kasus ini, algoritma melakukan pembagian tabel hingga ukuran tabel sebesar 1 elemen. Jumlah langkah tersebut adalah 2log n. Karena pada setiap langkah dilakukan perbandingan yang merupakan basis dari penghitungan kompleksitas waktu algoritma pencarian, maka kompleksitas waktu terburuk algoritma ini adalah 2log n.

Algoritma dalam bentuk pseudocode dari pencarian biner adalah sebagai berikut.

procedure binary_search(x: integer; a1, a2, …, an:

integers)

i := 1 {i is left endpoint of search interval}

j := n {j is right endpoint of search interval}

while (i < j) begin m := ⎣(i + j)/2⎦ if x > am then i := m + 1 else j := m end if x = ai then location := i else location := 0{

letak dari elemen yang dicari adalah subscript dari suku yang sama dengan x, atau nol jika tidak ditemukan.} Jelas bahwa dalam barisan yang terurut, pencarian biner lebih efisien daripada pencarian liniar. Selanjutnya muncul pertanyaan bagaimana cara menganalisa efisiensi dari suatu algoritma? Kita dapat mengukur efisiensi ini dengan

Waktu (time): yakni banyaknya komputasi elementer dalam algoritma
Ruang (space): adalah banyaknya sel memori yang dibutuhkan oleh algoritma.

Ukuran ini secara berturut-turut disebut sebagai kompleksitas komputasi (computational complexity) dan kompleklsitas ruang (space complexity). Berapakah kompleksitas waktu dari algoritma pencarian linier ? Kita akan menentukan banyaknya proses perbandingan pada kasus terburuk (worst-case) sebagai fungsi dari panjang barisan n. Kasus terburuk dari algoritma pencarian linier muncul ketika elemen yang dicari 2. Algoritma, Kompleksitas dan Teori Bilangan - 3 ternyata tidak ada didalam barisan masukan. Pada kasus tersebut, setiap suku dalam barisan akan dibandingkan dengan elemen yang dicari. Sehingga, untuk n buah elemen, loop while (i ≤ n and x ≠ ai) i := i + 1 dilaksanakan n kali, sehingga memerlukan 2n buah proses perbandingan. Saat memasuki loop ke (n+1) kalinya, yang dieksekusi hanyalah perbandingan i ≤ n dan loop diakhiri. Akhirnya perbandingan if i ≤ n then location := i dieksekusi, sehingga pada kasus terburuk kompleksitas waktu adalah 2n + 2. Ini adalah nilai kompleksitas dari algoritma pencarian linier.

Selanjutnya, berapakah kompleksitas waktu dari algoritma pencarian biner? Sekali lagi kita akan menentukan jumlah perbandingan pada kondisi terburuk sebagai fungsi dari banyaknya suku dalam deretan n. Kita asumsikan terdapat n=2k buah elemen di dalam barisan yang berarti bahwa k = log(n). Jika n bukan pangkat 2 dari suatu bilangan, barisan tersebut dapat dianggap sebagai bagian dari barisan lain yang lebih besar, dimana 2k am then i := m + 1 else j := m end interval pencarian dibatasi pada (2 k –1) buah elemen,

menggunakan dua operasi perbandingan. Pada siklus kedua, interval pencarian dibatasi pada sejumlah 2 k-2 elemen, sekali lagi dengan dua buah perbandingan. Proses ini diulangi terus hingga terdapat hanya satu buah (=2 0 ) 2. Algoritma, Kompleksitas dan Teori Bilangan - 4 elemen tersisa dalam interval pencarian. Pada kondisi ini, sejumlah 2k perbandingan telah dilakukan. Kemudian, dilakukan perbandingan: while (i < j). Setelah itu keluar dari loop dan perbandingan akhir adalah if x = ai then location := i Menentukan apakah elemen yang dicari sudah ketemu. Dengan demikian, total dari kompleksitas waktu untuk algoritma pencarian biner adalah 2k + 2 = 2 ⎡log(n)⎤ + 2.

(NB: kita selalu mengasumsikan logaritma basis dua). Pada umumnya, untuk input yang kecil, kita tidak tertarik pada kompleksitas ruang maupun waktu. Perbedaan kompleksitas waktu untuk pencarian linier dengan pencarian biner tidak begitu berarti untuk n=10, tetapi sangat signifikan untuk n = 2 30 . Misalkan, ada dua buah algoritma, sebut sebagai algoritma A dan algoritma B yang dapat memecahkan suatu kelas permasalahan. Kompleksitas waktu dari algoritma A adalah 5000n sedangkan kompleksitas dari algoritm B adalah ⎡1.1 n ⎤ untuk masukan n buah elemen (barisan).

Sekarang kita perhatikan perbandingan kompleksitas waktu dari algoritma A dan B sebagai berikut: Besarnya masukan Kompleksitas algoritma-A Kompleksitas algoritma-B n 5000n ⎡1.1 n ⎤ 10 50.000 3 100 500.000 13.781 1.000 5.000.000 2.5×10 41 1000.000 5×10 9 4,8×10 41392 Ini berarti bahwa algoritma B tidak dapat dipakai untuk masukan dengan elemen yang besar, sedangkan dengan algoritma A, hal ini masih bisa diatasi. Jadi, yang paling penting dalam menghitung kompleksitas suatu algoritma adalah pertumbuhan dari fungsi kompleksitas. Pertumbuhan dari kompleksitas dengan meningkatnya besarnya masukan, n, adalah ukuran yang sesuai untuk membandingkan algoritma. Pertumbuhan fungsi kompleksitas dilambangkan dengan notasi O (dibaca big-O). Perhatikan definisi berikut ini.