Algoritma pencarian biner: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
k Bot: Penggantian teks otomatis (-algoritma; +algoritme) |
Penambahan link divide and conquer (ID) Tag: Suntingan perangkat seluler Suntingan peramban seluler Tugas pengguna baru Disarankan: tambahkan pranala |
||
| (12 revisi perantara oleh 11 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)
* Apakah angka lebih besar dari 12? (Tidak)
* Apakah angka lebih besar dari 10? (Ya)
* Apakah
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).
| |||