Algoritma pencarian biner: Perbedaan antara revisi

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 te7ngahtengah (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]]).

BuPenerapanPenerapan 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 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.

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.