Algoritma pencarian biner: Perbedaan antara revisi

 

'''function''' binarySearch(a, value, left, right)

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

'''if''' a[mid] = value

Ada beberapa hal yang tidak terkait dengan komputer dimana sebuah pemilahan biner adalah cara tercepat untuk mengisolasi sebuah solusi yang dicari. Pada pemecahan sebuah permasalah dengan banyak kemungkinan penyebab, kita dapat mengubah setengah sangkaan, kita lihat apakah permasalahan masih terjadi dan tentukan bagian setengah berikutnya; ubah setengah sangkaan sisanya, dan seterusnya.

 

 

== Dukungan Bahasa ==

Banyak pustaka standard menyediakan suatu cara untuk pencarian biner. [[Bahasa pemrograman C|C]] menyediakan <code>bsearch</code> dalam pustaka standardnya. [[Standard Template Library|STL]]-nya [[C++]] menyediakan [[fungsi algoritma]] <code>[[lower bound]]</code> dan <code>[[upper bound]]</code>. [[Java (sun)|Java]] menyediakan sebuah himpunan method statik ''overloded'' <code>binarySearch</code> dalam kelas {{JavaDoc:SE|package=java.util|java/util|Arrays}} untuk melakukan pencarian biner pada array java.

 

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]], algoritma-algoritma yang mengasihlan jawaban sederhana berupa ya/tidak.

 

Sebagai contoh, anggap kita dapat menjawab "Apakah matriks ''n'' x ''n'' ini memiliki [[determinan]] lebih besar dari ''k''?" dalam waktu O(''n''²). Kemudian, dengan memanfaatkan pencarian biner, kita dapat menemukan (batas atas) determinan tersebut dalam waktu O(''n''²log ''d''), dimana ''d'' adalah determinan; sebagai catatan, d bukanlah ukuran dari masukan tetapi ukuran dari keluaran.

 

* [[Pencarian biner seragam]]

* [[Notasi O besar]]

 

== References ==

 

[[Kategori:Algoritma]]

[[de:Binäre Suche]]

[[es:Búsqueda binaria]]

[[fr:Dichotomie]]

[[it:Ricerca dicotomica]]

[[pt:Pesquisa binária]]

[[sk:Binárne vyhladávanie]]