Simulic
Bahasa Indonesia

Pencarian sekuensial vs. pencarian biner – menghitung perbandingan

InformatikaAlgoritma dan pemecahan masalahUsia 12–13

Simulic.comMemuat…

Gunakan di kelas saya

Larik dan nilai target yang sama dijalankan melalui pencarian sekuensial (menelusuri dari awal) dan pencarian biner (membagi dua rentang pada larik terurut) secara berdampingan. Siswa mengeklik Langkah atau Putar untuk melihat sel yang sedang dibandingkan, rentang yang dibuang, dan jumlah perbandingan tiap algoritma; mengeklik sel mengubah nilai target, dan mematikan pengurutan menunjukkan mengapa pencarian biner tidak lagi berfungsi.

Pelajaran: Algoritma pencarian sekuensial; algoritma pencarian biner

Yang ditunjukkan

Pencarian sekuensial memeriksa elemen satu per satu dari awal, sehingga dalam kasus terburuk dibutuhkan perbandingan sebanyak jumlah elemen. Pencarian biner membandingkan nilai target dengan elemen tengah larik yang terurut dan membuang separuh yang tidak mungkin memuatnya, sehingga paling banyak dibutuhkan sekitar log₂n + 1 perbandingan, hanya lima untuk enam belas elemen. Menghitung perbandingan kedua algoritma pada larik yang sama menunjukkan mengapa pencarian biner unggul pada daftar panjang, dan mengapa ia sepenuhnya bergantung pada data yang sudah terurut.

Cara menggunakan

Atur Algoritma ke Keduanya (bandingkan), pilih Jumlah elemen, lalu klik Langkah untuk mengikuti setiap perbandingan: sel yang disorot, penanda low, mid, dan high, serta bagian larik yang dibuang. Klik sebuah sel untuk mengganti nilai target, atau gunakan Putar untuk menjalankan sampai selesai. Coba target di dekat awal larik, lalu matikan Larik terurut naik untuk melihat mengapa pencarian biner tidak bisa lagi digunakan.

Parameter yang dapat diubah

  • Jumlah elemen 5–20
  • Nilai target (0 = pilih acak dari larik) 0–99
  • Algoritma Keduanya (bandingkan), Pencarian sekuensial, Pencarian biner
  • Larik terurut naik
  • Kecepatan jalan 1–5 langkah/s

Pertanyaan untuk dijelajahi

  1. Berapa jumlah perbandingan terbanyak yang dibutuhkan pencarian biner untuk menemukan nilai dalam larik berisi 16 elemen?
  2. Untuk nilai target mana pencarian sekuensial membutuhkan lebih sedikit perbandingan daripada pencarian biner?
  3. Mengapa pencarian biner tidak bisa digunakan jika larik tidak terurut?

Simulasi terkait