Pencarian Biner dan Syarat Data Terurut
PT-INF-VIII-011
Menelusuri pembagian rentang pencarian dan menjelaskan prasyaratnya.
Bekal awal: Memahami pencarian berurutan serta urutan kode.
Jejak Ponpes Temas
Model bacaan melanjutkan konteks peminjaman dan pengembalian. Kode, urutan, dan hasil pencarian adalah simulasi; tidak mengubah katalog aplikasi Pustaka.
Kartu Sumber dan Kasus
3A · Satu Target, Dua Cara Mencari
Jejak algoritma simulasi
Seluruh data, tokoh, berkas, dan hasil baru pada kartu ini adalah simulasi/rekaan pembelajaran; bukan katalog, pengguna, fasilitas, atau kejadian nyata Ponpes Temas.
| Target | Linear: perbandingan | Biner: perbandingan | Hasil |
|---|---|---|---|
| B01 | 1 | 2 | Ditemukan |
| B05 | 5 | 2 | Ditemukan |
| B06 | 6 | 3 | Ditemukan |
| B00 | 6 | 2 | Tidak ditemukan |
| B07 | 6 | 3 | Tidak ditemukan |
Daftar kode untuk kedua cara adalah B01, B02, B03, B04, B05, B06 dalam urutan naik. Satu perbandingan berarti membandingkan target dengan satu elemen, bukan seluruh operasi atau waktu komputer. Bentuk kode adalah B diikuti dua digit; b05 boleh dinormalkan ke B05, tetapi B7 tidak otomatis ditambah digit.
Linear memeriksa dari awal hingga cocok atau habis. Biner memakai indeks 0–5, dengan tengah bagian bulat dari (kiri + kanan)/2. Jika target lebih kecil, kanan menjadi tengah − 1; jika lebih besar, kiri menjadi tengah + 1. Rentang selalu mengecil. Kiri melebihi kanan berarti tidak ditemukan.
Untuk B05, linear memeriksa lima elemen; biner B03 lalu B05, dua elemen. Untuk B01, linear satu elemen dan biner B03 lalu B01, dua. Untuk B06, biner B03, B05, B06, tiga. B00 tidak ditemukan setelah biner B03, B01; B07 setelah B03, B05, B06. Kecepatan tiap target berbeda; biaya menyiapkan urutan juga perlu dipertimbangkan.
Fokus pemeriksaan. Biner memakai urutan yang benar; bandingkan definisi hitungan dan data yang sama.
Urutan memberi informasi
Pencarian biner memakai data yang sudah terurut menurut kunci dan aturan pembanding yang sama. Pada daftar kode B01–B06, target dibandingkan dengan elemen tengah. Jika target lebih besar, bagian yang lebih kecil dapat dikeluarkan dari rentang pencarian; jika lebih kecil, bagian sebaliknya dikeluarkan. Tanpa urutan yang benar, pembuangan bagian itu tidak dapat dipercaya.
Tetapkan aturan titik tengah
Model memakai indeks 0–5 dan tengah sebagai bagian bulat dari (kiri + kanan)/2. Untuk B05, rentang awal 0–5 memberi tengah 2, yaitu B03. Target lebih besar sehingga kiri menjadi 3. Rentang 3–5 memberi tengah 4, yaitu B05; ditemukan dalam dua perbandingan elemen. Perubahan batas harus mengecilkan rentang.
Efisiensi perlu konteks
Biner sering mengurangi banyak perbandingan pada data besar terurut, tetapi penyiapan urutan mempunyai biaya. Pada data ini, B01 ditemukan linear dalam satu perbandingan, sedangkan biner memerlukan dua. Jika kiri melewati kanan, target tidak ada. Alat tidak boleh menampilkan salah satu baris sebagai pengganti ketika pencarian gagal.
Telusuri contoh
Telusuri B06.
- Rentang 0–5: tengah 2, B03; ambil kanan.
- Rentang 3–5: tengah 4, B05; ambil kanan.
- Rentang 5–5: B06 cocok, tiga perbandingan.
Mengapa cara biner tidak sah pada daftar acak?
- Posisi tengah tidak menjamin bagian kiri lebih kecil.
- Membuang setengah daftar dapat membuang target yang dicari.
- Urutkan dengan kunci serta pembanding yang sama lebih dahulu.
Pencarian biner memerlukan urutan yang benar; cepat pada satu kasus bukan jaminan selalu terbaik.
Latihan mandiri
1 Apa prasyarat penting pencarian biner?
Petunjuk awal
Tentukan sumber, konsep, dan bukti. Jelaskan alasan serta batas simpulan; jangan menambahkan data yang belum tersedia.
Pembahasan · buka setelah mencoba
Data terurut menurut kunci serta aturan pembanding yang sama dengan pencarian.
2 Tuliskan dua kode yang diperiksa saat mencari B05.
Petunjuk awal
Tentukan sumber, konsep, dan bukti. Jelaskan alasan serta batas simpulan; jangan menambahkan data yang belum tersedia.
Pembahasan · buka setelah mencoba
B03 lalu B05 menurut aturan titik tengah model.
3 Kapan pencarian berakhir tidak ditemukan?
Petunjuk awal
Tentukan sumber, konsep, dan bukti. Jelaskan alasan serta batas simpulan; jangan menambahkan data yang belum tersedia.
Pembahasan · buka setelah mencoba
Saat rentang kosong, yaitu batas kiri lebih besar daripada kanan, tanpa kecocokan.
4 Apakah biner selalu lebih sedikit perbandingan daripada linear pada tiap target?
Petunjuk awal
Tentukan sumber, konsep, dan bukti. Jelaskan alasan serta batas simpulan; jangan menambahkan data yang belum tersedia.
Pembahasan · buka setelah mencoba
Tidak; B01 pada model ditemukan linear dalam satu dan biner dalam dua perbandingan. Perbandingan umum perlu konteks ukuran serta biaya pengurutan.
Perluas pemahamanmu
Telusuri B00 dan B07 yang tidak ada. B00 membandingkan B03 lalu B01; B07 membandingkan B03, B05, B06. Jelaskan mengapa rentang akhirnya kosong.
Coba dengan umpan balik
Latihan otomatis membantu pemeriksaan; tuliskan alasan dan langkah untuk membuktikan pemahaman.
1 Elemen tengah pertama pada indeks 0–5 ialah indeks…
Petunjuk awal
Tentukan sumber, konsep, dan bukti. Jelaskan alasan serta batas simpulan; jangan menambahkan data yang belum tersedia.
Pembahasan · buka setelah mencoba
A. 2. Bagian bulat 2,5 adalah 2 pada aturan model.
2 B05 pada model biner diperiksa melalui…
Petunjuk awal
Tentukan sumber, konsep, dan bukti. Jelaskan alasan serta batas simpulan; jangan menambahkan data yang belum tersedia.
Pembahasan · buka setelah mencoba
D. B03 lalu B05. Rentang dipersempit setelah membandingkan B03.
3 Menggunakan biner pada data acak dapat…
Petunjuk awal
Tentukan sumber, konsep, dan bukti. Jelaskan alasan serta batas simpulan; jangan menambahkan data yang belum tersedia.
Pembahasan · buka setelah mencoba
B. membuang bagian yang memuat target. Kesimpulan tentang setengah rentang bergantung pada data terurut.
Coba di Ponpes Temas
Buat tabel kiri–kanan–tengah–kode untuk target rekaan. Cocokkan dengan bengkel web yang memakai data dan aturan tengah sama.
Penanda pribadi di perangkat ini; bukan nilai atau bukti penguasaan.