Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-23T03:09:26Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 23 Agustus 2026 03.09
Baris 87:		Baris 87:
	* [http://mathworld.wolfram.com/BinarySearch.html Mathworld: Binary search]		* [http://mathworld.wolfram.com/BinarySearch.html Mathworld: Binary search]

	== ~~Referensi~~ ==		== Sumber dan atribusi ==
	* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.2.1: Searching an Ordered Table, pp. 409–426.

	== ~~Sumber dan atribusi ==~~		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Algoritma+pencarian+biner&oldid=29187966 Wikipedia bahasa Indonesia], revisi 29187966 (2026-05-02T15:36:05Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

	~~Artikel ini diadaptasi dalam mode teks dari~~		<!-- WIKI_UNISSULA_PRESENTATION_V4 -->
	~~[https://id.wikipedia.org/w/index.php?title=Algoritma_pencarian_biner&oldid=29187966 Wikipedia bahasa Indonesia],~~
	~~revisi 29187966 (2026~~-05-~~02T15:36:05Z).~~
	~~Gambar, media, infobox, templat navigasi, dan kategori sumber~~
	~~tidak diimpor ke Wiki Unissula.~~
	~~Atribusi dan lisensi mengikuti ketentuan Creative Commons~~
	~~Atribusi~~-~~BerbagiSerupa (CC BY~~-~~SA) pada sumber Wikipedia.~~

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187966; atribusi sumber disertakan.

2026-08-23T02:32:09Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187966; atribusi sumber disertakan.

Halaman baru

Sebuah '''algoritma 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 [[Bagi dan atasi|algoritme divide and conquer]] (atau lebih khusus algoritma decrease and conquer) dan sebuah [[pencarian dikotomi]] (lebih rinci di [[Algoritme pencarian]]).

== Algoritma ==
Penerapan terbanyak dari pencarian biner adalah untuk mencari sebuah nilai tertentu dalam sebuah [[Algoritme 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.

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. Berikut ini adalah ''pseudocode'' sederhana yang menentukan indeks (posisi)
dari nilai yang diberikan dalam sebuah list berurut, ''a'' berada antara ''left'' dan ''right'':

'''function''' binarySearch(a, value, left, right)
'''if''' right < left
'''return''' ''not found''
mid:= floor((right-left)/2)+left
'''if''' a[mid] = value
'''return''' mid
'''if''' value < a[mid]
'''return''' binarySearch(a, value, left, mid-1)
'''else
'''return''' binarySearch(a, value, mid+1, right)

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

'''function''' binarySearch(a, value, left, right)
'''while''' left ≤ right
mid:= floor((right-left)/2)+left
'''if''' a[mid] = value
'''return''' mid
'''if''' value < a[mid]
right:= mid-1
'''else
left:= mid+1
'''return''' ''not found''

Pada kedua kasus, algoritma 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 [[algoritme 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.

== Contoh ==
Sebuah contoh aksi pencarian biner adalah sebuah permainan tebak-tebakan di mana 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 angka lebih besar dari 8? (Ya)
* Apakah angka lebih besar dari 12? (Tidak)
* Apakah angka lebih besar dari 10? (Ya)
* Apakah angka lebih besar dari 11? (Tidak)

Sehingga, angka tersebut pasti 11. Pada setiap langkah, kita memilih sebuah angka yang tepat berada di tengah-tengah jangkauan nilai-nilai yang mungkin. Sebagai contoh, saat kita mengetahui angka tersebut lebih besar dari 8, tetapi lebih kecil atau sama dengan 12, kita mengetahui untuk memilih angka di tengah-tengah jangkauan [9, 12] (pada kasus ini 10 adalah yang optimal).

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 algoritma umum, karena angka tersebut dibatasi oleh sebuah jangkauan tertentu.

Walaupun angka yang kita tebak sangat banyak, pada kasus tidak ada batas atas ''N'', kita masih dapat
menemukan angka paling banyak dalam <math>2\lceil \log_2 k \rceil</math> langkah (di mana k adalah angka
yang dipilih (yang tidak diketahui)), caranya adalah dengan pertama-tama menemukan sebuah batas atas
dengan melipatduakannya. Sebaai contoh, jika angka tersebut adalah 11, kita dapat menggunakan
urutan tebakan sebagai berikut untuk menemukannya:

* Apakah angka lebih besar dari 1? (Ya)
* Apakah angka lebih besar dari 2? (Ya)
* Apakah angka lebih besar dari 4? (Ya)
* Apakah angka lebih besar dari 8? (Ya)
* Apakah angka lebih besar dari 16? (Tidak, N=16, lakukan seperti di atas)
(Kita mengetahui angka tersebut lebih besar dari 8)
* Apakah angka lebih besar dari 12? (Tidak)
* Apakah angka lebih besar dari 10? (Ya)
* Apakah angka lebih besar dari 11? (Tidak)

Satu penerapan sederhan, pada sistem [[kendali revisi]], dimungkinkan memanfaatkan sebuah pencarian biner untuk melihat pada revisi mana sebuah cuplikan isi ditambahkan ke sebuah file. Dengan mudah kita lakukan sebuah pencarian biner terhadap seluruh ''history'' versi; jika isi tidak ada dalam suatu versi, suatu saat kemudian pasti akan muncul, dan jika ada pasti muncul di versi tersebut atau versi berikutnya. Cara ini lebih cepat dibandingkan dengan memeriksa setiap perbedaan antar versi.

Ada beberapa hal yang tidak terkait dengan komputer di mana 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 masalah masih terjadi dan tentukan bagian setengah berikutnya; ubah setengah sangkaan sisanya, dan seterusnya.

Contoh nyata lainnya: pada satu revisi di antara 500 revisi terakhir, sebuah paragraf penting terhapus dari sebuah artikel Wikipedia—pertanyaanya di revisi mana? Kita menghadapai paling banyak 500 opersi pembandingan, atau 9 pembandingan dengan pemilahan biner (2 pangkat 9, yaitu 512).

== Penerapan pada [[teori kompleksitas komputasi|teori kompleksitas]] ==
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''<sup>2</sup>). Kemudian, dengan memanfaatkan pencarian biner, kita dapat menemukan (batas atas) determinan tersebut dalam waktu O(''n''<sup>2</sup>log ''d''), di mana ''d'' adalah determinan; sebagai catatan, d bukanlah ukuran dari masukan tetapi ukuran dari keluaran.

== Lihat pula ==
* [[Pencarian biner seragam]]
* [[Notasi O besar]]

== Link-link luar ==
* [http://www.nist.gov/dads/HTML/binarySearch.html NIST Dictionary of Algorithms and Data Structures: binary search]
* Tim Bray. [http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary On the Goodness of Binary Search]. A short essay on the advantages of binary search and some Java sample code.
* [http://www.sparknotes.com/cs/searching/binarysearch/ Sparknotes: Binary search]. Simplified overview of binary search.
* [http://mathworld.wolfram.com/BinarySearch.html Mathworld: Binary search]

== Referensi ==
* [[Donald Knuth]]. ''The Art of Computer Programming'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.2.1: Searching an Ordered Table, pp. 409–426.

== Sumber dan atribusi ==

Artikel ini diadaptasi dalam mode teks dari
[https://id.wikipedia.org/w/index.php?title=Algoritma_pencarian_biner&oldid=29187966 Wikipedia bahasa Indonesia],
revisi 29187966 (2026-05-02T15:36:05Z).
Gambar, media, infobox, templat navigasi, dan kategori sumber
tidak diimpor ke Wiki Unissula.
Atribusi dan lisensi mengikuti ketentuan Creative Commons
Atribusi-BerbagiSerupa (CC BY-SA) pada sumber Wikipedia.

Algoritma pencarian biner - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29187966; atribusi sumber disertakan.