Meet in the Middle
Membagi dua eksponen dengan membagi pencarian
Meet in the Middle adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Saat Mencoba Semua Kemungkinan Terlalu Lambat
Beberapa persoalan memiliki N sekitar 40, sehingga mencoba semua 2^N himpunan bagian tidak mungkin dilakukan. Metode temu di tengah menyelamatkan persoalan berukuran menengah ini. 🤝
Gagasan Inti
Bagi masukan menjadi dua bagian. Selesaikan setiap bagian dengan mencoba semua kemungkinan, lalu gabungkan kedua hasil parsial tersebut secara cerdas.
Membagi Eksponen Menjadi Dua
Dua bagian berukuran N/2 masing-masing membutuhkan 2^(N/2), bukan total 2^N. Penyusutan sebesar akar kuadrat ini mengubah 2^40 menjadi 2^20 yang lebih mudah ditangani.
Target Klasik: Jumlah Himpunan Bagian
Tanyakan apakah ada himpunan bagian yang jumlahnya sama dengan target T. Jumlah himpunan bagian dengan N mendekati 40 adalah persoalan temu di tengah yang klasik.
Mengenumerasi Bagian Pertama
Daftarkan setiap jumlah himpunan bagian dari bagian kiri dan simpan semuanya. Dengan N/2 elemen, jumlahnya hanya 2^(N/2).
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []Mengenumerasi Bagian Kedua
Lakukan hal yang sama untuk bagian kanan dan buat daftar lengkap jumlah himpunan bagiannya. Sekarang Anda memiliki dua daftar yang mudah ditangani.
Menggabungkan dengan Pencarian
Untuk setiap jumlah kanan r, Anda memerlukan jumlah kiri yang sama dengan T dikurangi r. Himpunan berbasis pencincangan atau daftar terurut membuat pemeriksaan ini cepat.
need = T - r
found = need in left_setDua Cara untuk Mencocokkan
Untuk target yang tepat, gunakan himpunan berbasis pencincangan. Untuk menghitung atau mencari jumlah terdekat, urutkan salah satu bagian lalu lakukan pencarian biner di dalamnya.
Biaya Waktu
Total pekerjaan kira-kira 2^(N/2) dikalikan faktor log untuk pencarian atau pengurutan. Kompleksitas inilah yang membuat N mendekati 40 dapat dikerjakan.
Memori adalah Komprominya
Anda menyimpan satu bagian lengkap, sehingga memori bertambah menjadi 2^(N/2). Simpan hanya yang diperlukan agar tetap berada dalam batas.
Kegunaan Lainnya
Selain jumlah himpunan bagian, gunakan metode ini untuk mencari himpunan bagian maksimum di bawah batas, menghitung pasangan, dan persoalan bergaya logaritma diskret. Metode ini cocok untuk pembagian yang jelas.
Pemeriksaan Singkat
Anda menerapkan metode temu di tengah pada persoalan himpunan bagian dengan N elemen. Berapa perkiraan biaya waktunya?
Rangkuman
Bagi menjadi dua bagian, coba semua kemungkinan pada masing-masing bagian, lalu cocokkan jumlah kiri dan kanan. Anda menukar sedikit memori dengan percepatan yang sangat besar. 🚀
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Meet in the Middle” gratis?
Ya — teks lengkap “Meet in the Middle” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Meet in the Middle”?
Membagi dua eksponen dengan membagi pencarian Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 3 dari 4.
Berapa lama pelajaran “Meet in the Middle” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?
Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- State Menang & Kalah dalam Permainan
- Nim dan Bilangan Grundy
- Meet in the Middle
- Debug Cepat: Stress Test & Triage