Pencarian Biner
Diperkenalkan| English | Makna |
|---|---|
| sorted/ˈsɔːtɪd/ | terurut |
| Binary search/ˈbaɪnəri sɜːtʃ/ | pencarian biner |
| target/ˈtɑːɡɪt/ | target |
| middle/ˈmɪdl/ | tengah |
| comparison/kəmˈpærɪsn/ | perbandingan |
| halves/hɑːvz/ | setengah |
| linear search/ˈlɪnɪə sɜːtʃ/ | pencarian linear |
Mencari dengan cepat dalam daftar terurut
- Pencarian biner adalah cara cepat untuk menemukan nilai target dalam daftar yang terurut.
- "Terurut" berarti nilainya berurutan — terkecil ke terbesar, misalnya.
- Jauh lebih cepat daripada memeriksa setiap item.
- Namun, ini memiliki satu persyaratan ketat.
Pencarian biner membutuhkan data terurut. Pada daftar yang tidak terurut, ia bisa melewatkan target dan melesetkannya. Selalu urutkan terlebih dahulu — atau gunakan pencarian berbeda.
Pencarian biner hanya dapat digunakan pada data yang:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Pada data yang tidak terurut, pencarian biner bisa melewatkan target.
Periksa bagian tengah, lalu kurangi separuh
- Ide-nya sederhana: periksa elemen tengah. Kemudian:
- jika tengah sama dengan target, Anda menemukannya;
- jika target lebih kecil, cari hanya setengah kiri;
- jika target lebih besar, cari hanya setengah kanan.
Pencarian linear vs pencarian biner
biner membagi dua rentang setiap langkah
Pencarian linear memeriksa setiap item; pencarian biner membagi dua daftar yang sudah diurutkan per pembandingan, sehingga membutuhkan jauh lebih sedikit langkah.
Jika target lebih besar dari elemen tengah, pencarian biner selanjutnya melihat di:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Target yang lebih besar harus berada di setengah kanan (yang lebih tinggi).
Setiap pembandingan dalam pencarian biner ______ bagian sisa dari daftar.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Pembagian dua setiap langkah adalah alasannya sangat cepat.
Kira-kira berapa banyak pengecekan pencarian biner yang dibutuhkan untuk daftar terurut berisi 1000 item? (2^10 = 1024)
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Karena 2^10 = 1024 ≥ 1000, sekitar 10 kali pembagian dua cukup.
Mengapa itu begitu cepat
- Setiap perbandingan memotong separuh bagian yang tersisa dari daftar.
- Untuk 1000 item, pencarian linear mungkin memerlukan hingga 1000 pengecekan.
- Pencarian biner membutuhkan paling banyak sekitar 10, karena $2^{10} = 1024$.
- Semakin besar daftar, semakin besar keuntungannya.
Pencarian biner menemukan 14 dalam [2,5,8,11,14,17,20] dalam berapa banyak pembandingan?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Tengah 11 → kanan; Tengah 17 → kiri; Tengah 14 → ditemukan: 3 pembandingan.
Pada daftar terurut yang besar, pencarian biner membutuhkan jauh lebih sedikit pembandingan daripada pencarian linear.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Pembagian dua mengalahkan pemeriksaan setiap item satu per satu.
Dibandingkan dengan pencarian linear
- Pencarian linear memeriksa setiap elemen satu per satu.
- Pencarian biner mengunggulinya pada daftar terurut yang besar dengan memotong separuh setiap langkahnya.
Cari [2, 5, 8, 11, 14, 17, 20] untuk nilai 14. Tengah adalah 11; 14 > 11 → cari setengah kanan [14, 17, 20]. Tengah adalah 17; 14 < 17 → cari [14]. Tengah adalah 14 — ditemukan hanya dalam 3 perbandingan. Pencarian linear akan memakan waktu 5.
Pencarian biner menemukan target dalam daftar terurut dengan memeriksa tengah dan menyisakan hanya setengah yang kemungkinan mengandung target tersebut. Setiap perbandingan memotong separuh rentang, sehingga 1000 item butuh ~10 pengecekan — jauh lebih sedikit daripada pencarian linear yang butuh 1000. Cara ini bekerja hanya pada data terurut.