Biaya algoritma dan syarat perbandingan
INFO9-08
Membandingkan jumlah langkah dengan memperhitungkan prasyarat serta pekerjaan persiapan.
Bekal awal: Memahami pencarian berurutan dan biner dari kelas VIII.
Konteks bab
Pembagian giliran adalah model belajar; aturan layanan nyata mengikuti pendamping. Kartu serta jaringan berikut rekaan.
Bacaan dan kasus
2 · Urutan yang berubah tanpa disadari
Bacaan pendalaman
Kasus dan angka yang dibuat untuk latihan adalah simulasi/rekaan; fakta konsep dan sumber dibedakan dalam uraian.
Permintaan berkode A,B,C masuk berurutan. Program model memakai tumpukan sehingga permintaan C keluar lebih dahulu. Pembuat menganggap hasilnya benar karena semua kode masih ada, tetapi petunjuk layanan menjanjikan urutan kedatangan. Masalahnya bukan hilangnya data, melainkan ketidaksesuaian struktur dengan kontrak.
Kelompok membandingkan antrean dan tumpukan di kertas. Mereka menambah D, mengambil dua entri, dan mencatat isi yang tersisa. Daftar langkah memperlihatkan perbedaan yang tidak terlihat dari sekadar jumlah entri. Urutan ternyata bagian penting dari makna data.
Pada tugas lain, mereka menggambar hubungan empat lokasi. Dua jalur mempunyai jumlah sisi sama, tetapi waktu berbeda setelah bobot ditambahkan. Mereka belajar bahwa struktur serta ukuran harus mengikuti pertanyaan. Lebih sedikit langkah, lebih dekat pada gambar, dan lebih cepat di dunia nyata tidak selalu berarti hal yang sama.
Fokus pemeriksaan. Mengapa jumlah entri yang benar belum menjamin perilaku layanan benar?
Lebih sedikit langkah perlu dasar yang sama
Pencarian berurutan memeriksa entri satu demi satu; pencarian biner mempersempit rentang pada data terurut. Pada daftar terurut [3,6,9,12,18,21,24,30], pencarian berurutan menemukan21 setelah enam pemeriksaan. Pencarian biner dengan titik tengah dibulatkan ke bawah memeriksa12 lalu21, dua pemeriksaan. Jenis operasi yang dihitung harus sama agar perbandingan bermakna.
Persiapan juga pekerjaan
Jika data belum terurut, pencarian biner memerlukan pengurutan atau struktur yang memang dijaga terurut. Untuk satu pencarian pada data kecil, biaya persiapan dapat lebih besar daripada manfaat mengurangi pemeriksaan. Untuk banyak pencarian pada data yang jarang berubah, persiapan mungkin berguna. Keputusan perlu mempertimbangkan jumlah pencarian, perubahan data, dan tujuan.
Ketepatan mendahului kecepatan
Algoritma cepat yang melanggar prasyarat dapat menghasilkan jawaban salah. Catat keadaan kosong, target tidak ada, duplikat, dan batas indeks. Hasil waktu pada satu perangkat juga dipengaruhi banyak faktor. Hitungan langkah model membantu penalaran, tetapi tidak menjadi jaminan durasi nyata untuk semua komputer.
Pencarian biner dengan penghitung pemeriksaan
data = [3, 6, 9, 12, 18, 21, 24, 30]
target = 21
kiri, kanan = 0, len(data) - 1
hasil, cek = -1, 0
while kiri <= kanan:
tengah = (kiri + kanan) // 2
cek += 1
if data[tengah] == target:
hasil = tengah
break
if data[tengah] < target:
kiri = tengah + 1
else:
kanan = tengah - 1
print(hasil, cek)Keluaran contoh
5 2
−1 dipakai sebagai penanda tidak ditemukan, bukan indeks untuk mengambil elemen. Uji target25 dan daftar kosong pada salinan kode.
Telusuri contoh
Mengapa target21 ditemukan pada pemeriksaan kedua biner?
- Indeks0–7, tengah3 bernilai12; target lebih besar.
- Rentang4–7, tengah5 bernilai21.
- Hasil indeks5, bukan posisi ke5; indeks dimulai0.
Apakah biner sah langsung pada [21,3,30,6]?
- Tidak memenuhi urutan menaik.
- Urutkan dengan menjaga hubungan catatan atau pilih pencarian berurutan.
- Hitung juga biaya persiapan jika membandingkan.
Kecepatan tidak membenarkan hasil salah; perbandingan yang mengabaikan persiapan dapat menyesatkan.
Latihan mandiri
1 Berapa pemeriksaan berurutan untuk21 pada daftar kasus?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
Enam.
2 Apa prasyarat pencarian biner?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
Data terurut sesuai aturan pembanding yang digunakan.
3 Mengapa biaya pengurutan perlu diperhitungkan?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
Merupakan pekerjaan tambahan sebelum pencarian, terutama jika data belum terurut.
4 Apa yang dibedakan antara indeks5 dan posisi?
Petunjuk awal
Pisahkan informasi yang diketahui, alasan yang diperlukan, dan batas kesimpulan. Periksa kembali contoh sebelum membuka pembahasan.
Pembahasan · buka setelah mencoba
Indeks5 ialah elemen keenam pada indeks mulai0.
Perluas pemahamanmu
Bandingkan satu pencarian dengan100 pencarian pada data yang tetap. Jelaskan secara kualitatif kapan persiapan lebih mungkin berguna tanpa mengarang waktu perangkat.
Coba dengan umpan balik
Latihan otomatis membantu pemeriksaan; tuliskan alasan dan langkah untuk membuktikan pemahaman.
1 Pencarian biner pada data belum terurut berisiko…
Petunjuk awal
Tentukan informasi, konsep dan bukti yang dibutuhkan.
Pembahasan · buka setelah mencoba
D. melewatkan target yang sebenarnya ada. Penyempitan rentang hanya benar jika prasyarat urutan dipenuhi.
Praktik dan refleksi
Telusuri pencarian target3,21, dan25 dengan dua cara. Catat indeks yang diperiksa, hasil, serta syarat berhenti.
Penanda pribadi di perangkat ini; bukan nilai atau bukti penguasaan.