Jelaskan Contoh dari Algoritma pencarian biner

Sebuah contoh aksi pencarian biner adalah sebuah permainan tebak-tebakan dimana seorang pemain harus menebak sebuah 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  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 algoritme 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  langkah (dimana 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 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.

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