Perbandingan
Masih mungkin
Pencarian linear perlu

  • Target
  • Masih mungkin
  • Dibandingkan
  • Tersisih
  • Ditemukan

Info lebih lanjut tentang pencarian biner

Pencarian biner

Pencarian biner menemukan nilai dalam daftar terurut dengan selalu melihat ke tengah. Jika nilai tengah terlalu kecil, target hanya bisa ada setelahnya; jika terlalu besar, hanya sebelumnya. Bagaimanapun, separuh dari sisanya tersingkir. Pilih nilai yang dicari, jalankan pencarian langkah demi langkah, dan lihat bagian yang diarsir menyusut sampai target ditemukan atau tidak ada yang tersisa. Tekan Putar untuk melihat pencarian, atau Langkah dan Mundur untuk maju satu langkah setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Garis putus-putus menandai nilai yang dicari, dan bagian yang diarsir adalah tempat nilai itu masih mungkin berada. Pencarian biner membutuhkan daftar terurut, jadi daftar yang belum terurut diurutkan dulu. Pilih nilainya, jumlah batang, atau ketik angka sendiri. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.

Cara kerjanya

  1. Pilih nilai yang dicari dan jumlah batang. Atau ketik angka sendiri: pencarian biner mengurutkannya dulu.
  2. Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu langkah setiap kali. Geser penggeser langkah untuk melompat ke mana saja dalam pencarian.
  3. Bandingkan kotak Perbandingan dengan Pencarian linear perlu, untuk nilai di dekat akhir atau nilai yang tidak ada.

Cara kerja pencarian biner

Catat bagian daftar terurut yang masih mungkin memuat target; awalnya itu seluruh daftar. Lihat nilai di tengahnya. Jika sama dengan target, selesai. Jika lebih kecil, target hanya bisa ada setelahnya, jadi lanjutkan dengan bagian setelah tengah. Jika lebih besar, lanjutkan dengan bagian sebelumnya. Jika tidak ada yang tersisa, target tidak ada dalam daftar.

Mengapa begitu cepat

Setiap perbandingan membagi dua bagian yang tersisa. Mulai dari n nilai, setelah k perbandingan tersisa paling banyak sekitar n/2ᵏ, jadi pencarian selesai setelah paling banyak ⌊log₂ n⌋ + 1 perbandingan: 6 untuk 40 nilai, 10 untuk 1.000, 20 untuk satu juta. Pencarian linear mungkin harus melihat setiap nilai. Syaratnya, daftar harus terurut, dan menjaganya tetap terurut, atau mengurutkannya dulu, juga ada biayanya.

Pertanyaan yang sering diajukan

Bagaimana cara kerja pencarian biner?

Ia membandingkan target dengan nilai tengah dari bagian daftar terurut yang masih mungkin memuatnya. Jika sama, target ditemukan; jika tidak, separuh yang tidak mungkin memuat target dibuang, dan pencarian berlanjut di separuh lainnya sampai target ditemukan atau tidak ada yang tersisa.

Berapa perbandingan yang dibutuhkan pencarian biner?

Paling banyak ⌊log₂ n⌋ + 1 untuk daftar berisi n nilai: 6 untuk 40, 10 untuk 1.000, 20 untuk satu juta. Setiap perbandingan membagi dua sisanya.

Mengapa pencarian biner membutuhkan daftar terurut?

Karena hanya dalam daftar terurut satu perbandingan memberi tahu di sisi mana target berada. Dalam daftar yang tidak terurut, nilai yang lebih kecil di tengah tidak berarti apa-apa tentang letak target, jadi tidak ada yang bisa disingkirkan.

Nilai mana yang ditemukan jika ada duplikat?

Salah satunya, tergantung di mana nilai tengahnya jatuh. Varian yang terus mencari ke kiri atau ke kanan setelah ada kecocokan menemukan kemunculan pertama atau terakhir.

Apakah angka saya dikirim ke mana pun?

Tidak. Pencarian berjalan di browser Anda, dan pengaturan terakhir Anda tersimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor