Algoritma pencarian biner: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Rayhan6726 (bicara | kontrib) k Rayhan6726 memindahkan halaman Algoritme encarian biner ke Algoritme pencarian biner: Perbaikan kesalahan pengetikkan |
Penambahan link divide and conquer (ID) Tag: Suntingan perangkat seluler Suntingan peramban seluler Tugas pengguna baru Disarankan: tambahkan pranala |
||
| (9 revisi perantara oleh 8 pengguna tidak ditampilkan) | |||
Baris 1:
Sebuah '''algoritme 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 algoritme decrease and conquer) dan sebuah [[pencarian dikotomi]] (lebih rinci di [[Algoritme pencarian]]).
== Algoritme ==
Baris 8:
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
'''if''' a[mid] = value
'''return''' mid
Baris 25:
'''function''' binarySearch(a, value, left, right)
'''while''' left ≤ right
mid
'''if''' a[mid] = value
'''return''' mid
'''if''' value < a[mid]
right
'''else
left
'''return''' ''not found''
Pada kedua kasus, algoritme 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 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 angka lebih besar dari 8? (Ya)
| |||