Algoritma pencarian biner: Perbedaan antara revisi

Sebuah '''algoritmaalgoritme pencarian biner''' (atau '''pemilahan biner''') adalah sebuah teknik untuk menemukan nilai tertentu dalam sebuah larik (''array'') linear, dengan menghilangkan setengah data pada setiap langkah, dipakai secara luas tetapi tidak secara ekslusif dalam [[ilmu komputer]]. Sebuah pencarian biner mencari nilai tengah (median), melakukan sebuah pembandingan untuk menentukan apakah nilai yang dicari ada sebelum atau sesudahnya, kemudian mencari setengah sisanya dengan cara yang sama. Sebuah pencarian biner adalah salah satu contoh dari [[algoritmaBagi dan atasi|algoritme divide and conquer]] (atau lebih khusus algoritmaalgoritme decrease and conquer) dan sebuah [[pencarian dikotomi]] (lebih rinci di [[AlgoritmaAlgoritme pencarian]]).

== AlgoritmaAlgoritme ==

Penerapan terbanyak dari pencarian biner adalah untuk mencari sebuah nilai tertentu dalam sebuah [[AlgoritmaAlgoritme pengurutan|list terurut]]. Jika dibayangkan, pencarian biner dapat dilihat sebagai sebuah permainan tebak-tebakan, kita menebak sebuah bilangan, atau nomor tempat, dari daftar (''list'') nilai.

dari nilai yang diberikan dalam sebuah list berurut, ''a'' berada antara ''left'' dan ''right'' :

mid := floor((right-left)/2)+left

Karena pemanggilan fungsi di atas adalah [[rekursif ekor]], fungsi tersebut dapat dituliskan sebagai sebuah pengulangan (''loop''), hasilnya adalah algoritmaalgoritme [[algoritmaalgoritme in-place|in-place]]:

mid := floor((right-left)/2)+left

right := mid-1

left := mid+1

Pada kedua kasus, algoritmaalgoritme akan berakhir karena paa setiap pemanggilan rekursif atau pengulangan, jangkauan indeks <code>right</code> dikurang <code>left</code> akan selalu mengecil, dan akhirnya pasti akan menjadi negatif.

Pencarian biner adalah sebuah [[algoritmaalgoritme logaritmik]] dan bekerja dalam waktu [[notasi O besar|O]](log n). Secara khusus, <math>1 + log_2N</math> 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.

Sebuah contoh aksi pencarian biner adalah sebuah permainan tebak-tebakan dimana seorang pemain harus menebak sebuah [[Bilangan asli|bilangan bulat positif]] yang dipilih oleh pemain lain di antara 1 dan ''N'', dengan memanfaatkan jawaban pertanyaan berupa ya dan tidak. Misalnya ''N'' adalah 16 dan angka yang dipilih adalah 11, permainan dapat berjalan sebagai berikut.

* Apakah angkatangka lebih besar dari 11? (Tidak)

Paling banyak ada <math>\lceil\log_2 N\rceil</math> pertanyaan yang dibutuhkan untuk mendapatkan angka tersebut, karena setiap pertanyaan menghilangkan setengah dari ruang pencarian. Sebagai catatan bahwa dibutuhkan kurang dari satu pertanyaan (iterasi) untuk algoritmaalgoritme umum, karena angka tersebut dibatasi oleh sebuah jangkauan tertentu.

Seandainya kita tidak mengetahui sebuah jangkauan yang tetap tempat dari bilangan ''k''berada, kita masih dapat menentukan nilainya dengan mengajukan <math>2\lceil\log_2k\rceil</math> pertanyaan ya/tidak dalam bentuk "Apakah ''k'' lebih besar dari ''x''?" untuk beberapa bilangan ''x''. Sebagai konsekuensi sederhana dari cara ini, jika kita dapat menjawab pertanyaan "Apakah nilai bilangan bulat ''k'' lebih besar dari nilai yang diberikan?" pada suatu waktu kemudian kita dapat menemukan nilai dari bilangan tersebut sama lamanya ditambah dengan faktor log ''k''. Hal ini disebut sebuah ''[[reduksi (kompleksitas)|reduksi]]'', dan karena disebabkan reduksi ini maka kebanyakan teoris kompleksitas berkonsentrasi pada [[permasalahan keputusan]], algoritmaalgoritme-algoritmaalgoritme yang mengasihlan jawaban sederhana berupa ya/tidak.

[[Kategori:AlgoritmaAlgoritme]]

[[Kategori:AlgoritmaAlgoritme Pencarian]]