Algoritma pencarian
| English | Bahasa Indonesia |
|---|---|
| linear search/ˈlɪnɪə sɜːtʃ/ | pencarian linear |
| binary search/ˈbaɪnəri sɜːtʃ/ | pencarian biner |
Dua puluh pertanyaan untuk satu juta nama
- Buku telepon berisi satu juta nama. Memeriksa mereka satu per satu, Anda akan membutuhkan setengah juta perbandingan sebelum menemukan nama yang diinginkan.
- Buka di tengah, tentukan separuh mana nama itu ada, dan buang separuh lainnya. Ulangi. Anda dapat menemukan nama apa pun hanya dalam dua puluh perbandingan.
- Setengah juta dibandingkan dengan dua puluh bukanlah penghematan kecil; ini adalah perbedaan antara program yang berfungsi dan program yang tidak bisa digunakan. Dan biayanya adalah satu hal: daftar harus sudah terurut.
- Pelajaran ini membahas pencarian linear dan pencarian biner, bagaimana kinerjanya masing-masing, dan bagaimana memilihnya.
Pencarian linear
FOR i ← 1 TO n
IF A[i] = target THEN
RETURN i
ENDIF
NEXT i
RETURN -1 // not found
- Algoritma ini berjalan dari awal, membandingkan setiap elemen dengan target, dan berhenti saat menemukan kecocokan atau mencapai akhir.
- Algoritma ini bekerja pada semua jenis daftar, terurut atau tidak, serta pada struktur apa pun yang dapat dilalui secara berurutan.
- Kasus terburuk: target berada di posisi terakhir atau tidak ada, sehingga semua $n$ elemen dibandingkan, yang bernilai $O(n)$. Rata-ratanya sekitar setengahnya.
Satu per satu, dari awal
Pencarian linear:
Pencarian linear tidak memerlukan persiapan dan bekerja pada daftar apa pun, dengan kompleksitas waktu terburuk O(n).
Pencarian linear adalah pilihan yang lebih baik ketika datanya:
Dengan tidak adanya urutan yang dapat dimanfaatkan (atau daftar yang sangat kecil), pencarian linear menghindari biaya pengurutan terlebih dahulu.
Pencarian biner
low ← 1 ; high ← n
WHILE low <= high DO
mid ← (low + high) DIV 2
IF A[mid] = target THEN
RETURN mid
ENDIF
IF A[mid] < target THEN
low ← mid + 1
ELSE high ← mid - 1
ENDWHILE
RETURN -1
- Algoritma ini mensyaratkan data harus terurut. Bandingkan elemen tengah dengan target: jika cocok, hentikan; jika target lebih besar, buang separuh bawah; jika tidak, buang separuh atas.
- Setiap perbandingan membagi dua rentang yang tersisa untuk dicari, sehingga jumlah perbandingan adalah $O(\log_2 n)$.
- Itulah mengapa satu juta item membutuhkan sekitar dua puluh perbandingan: $2^{20}$ sedikit melebihi satu juta.
Algoritma pencarian
biner membagi dua rentang setiap langkah
Linear memeriksa setiap item; biner membagi dua daftar terurut — jauh lebih sedikit perbandingan.
Kompleksitas waktu kasus terburuk dari pencarian biner adalah:
Mengurangi rentang menjadi setengah setiap langkah memberikan jumlah perbandingan yang logaritmik.
Kira-kira berapa banyak perbandingan yang dibutuhkan pencarian biner untuk satu juta item terurut?
$\log_2(1\,000\,000) \approx 20$ — sekitar 20 perbandingan.
Pencarian biner dapat digunakan pada daftar apa pun, terurut atau tidak.
Algoritma ini memutuskan bagian mana yang harus dibuang dengan membandingkan elemen tengah, yang hanya bermakna jika datanya sudah berurutan.
Pencarian biner memiliki kompleksitas O(log n) karena setiap perbandingan ____ rentang yang masih harus dicari.
Dua puluh kali pembagian dua menurunkan satu juta menjadi satu, itulah sebabnya 2^20 yang sedikit melebihi satu juta adalah angka yang perlu diingat.
Contoh terpecahkan: telusuri pencarian biner
- Daftar terurut adalah 2, 5, 8, 12, 16, 23, 38, 56, 72, 91. Telusuri pencarian untuk angka 23.
lowadalah 1,highadalah 10, sehinggamidadalah 5, menyimpan nilai 16. Karena 16 kurang dari 23, buang separuh bawah:lowmenjadi 6.low6,high10, sehinggamidadalah 8, menyimpan nilai 56. Karena 56 lebih besar dari 23, makahighmenjadi 7.low6,high7, sehinggamidadalah 6, menyimpan nilai 23. Ditemukan, dalam tiga perbandingan, padahal pencarian linear membutuhkan enam.- Tampilkan
low,high,mid, dan nilai pada setiap langkah. Sebagian besar poin ada pada proses pelacakan, bukan pada jawaban akhirnya.
Dalam daftar terurut 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, berapa banyak perbandingan yang dibutuhkan pencarian biner untuk menemukan 23?
mid 5 bernilai 16 (terlalu kecil), mid 8 bernilai 56 (terlalu besar), mid 6 bernilai 23. Pencarian linear akan membutuhkan enam perbandingan.
Memilih di antara keduanya
| linear | biner | |
|---|---|---|
| data harus terurut | tidak | ya |
| perbandingan, kasus terburuk | $n$ | $\log_2 n$ |
| satu juta item | hingga 1,000,000 | sekitar 20 |
| cocok untuk | daftar tak terurut atau kecil, daftar linked | array terurut besar, dicari berulang kali |
- Mengurutkan terlebih dahulu membutuhkan biaya lebih tinggi daripada satu kali pencarian linear, sehingga pencarian biner hanya menguntungkan jika daftar sudah terurut atau akan dicari berkali-kali.
- Pencarian biner juga memerlukan akses langsung ke elemen tengah, yang dimiliki oleh array tetapi tidak oleh daftar linked.
Contoh terpecahkan: bentangkan pilihan
- Sebuah program mencari daftar tak terurut berisi 50 rekaman hanya sekali. Pencarian linear: mengurutkan daftar terlebih dahulu akan memakan biaya jauh lebih besar daripada 50 perbandingan yang dibutuhkan pencarian.
- Sebuah program mencari array terurut berisi satu juta rekaman ribuan kali per detik. Pencarian biner: datanya sudah terurut dan setiap pencarian hanya membutuhkan sekitar 20 perbandingan alih-alih hingga satu juta.
- Sebuah program mencari daftar linked. Pencarian linear: pencarian biner perlu melompat langsung ke elemen tengah, dan daftar linked hanya dapat diikuti dari awal.
- Sebutkan nama algoritmanya, kemudian sifat data yang menjadikannya pilihan.
Cocokkan setiap metode pencarian dengan fakta utamanya.
Pencarian biner jauh lebih cepat (O(log n)) tetapi hanya pada data terurut; pencarian linear bekerja di mana saja dengan kompleksitas O(n).
Kapan pencarian linear merupakan pilihan yang lebih baik? Pilih semua yang berlaku.
Kasus terakhir adalah tempat di mana pencarian biner menang. Pengurutan terlebih dahulu lebih mahal daripada satu kali pencarian linear, sehingga hanya menguntungkan jika dilakukan pencarian berulang kali.
Biaya menjaga file tetap terurut
- Pencarian biner hanya tersedia pada daftar yang terurut, dan pengurutan tersebut tidak gratis. Soal yang meminta Anda untuk memberikan justifikasi atas sebuah pilihan berarti meminta Anda untuk menghitung biayanya.
- Jika data dicari sering dan jarang diubah, urutkan sekali dan setiap pencarian selanjutnya adalah $\log_2 n$. Ini berlaku untuk kamus atau tabel referensi.
- Jika data selalu berubah, setiap penyisipan harus mempertahankan urutan, yang membutuhkan perpindahan elemen-elemen berikutnya. Dalam kondisi ini, pencarian linear atas data tak terurut bisa menjadi total biaya yang lebih murah.
- Angka membuat argumen ini konkret: satu juta rekaman membutuhkan hingga satu juta perbandingan secara linear, namun hanya 20 dengan pencarian biner, karena $2^{20} > 10^6$.
- Jadi, jawaban yang mendapat nilai penuh menyebutkan keduanya: seberapa sering data dicari, dan seberapa sering data berubah.
Susun alasan pemilihan algoritma pencarian secara berurutan.
Pertanyaan pembenaran meminta trade-off, bukan pemenang. Pencarian biner pada daftar yang terus berubah bisa memakan biaya total lebih besar daripada pencarian linear.
⟦⟧ Nilai yang sering terlewat
- Pencarian biner membutuhkan data yang sudah terurut. Menyatakan "lebih cepat" tanpa syarat tersebut akan kehilangan nilai.
- Setiap langkah mengurangi rentang menjadi setengah, di sinilah $\log_2 n$ berasal dari. Berikan alasannya, bukan sekadar notasinya.
- Kedua pencarian harus mampu melaporkan tidak ditemukan, yang merupakan tujuan dari
-1dan kondisi perulangan. - Pencarian biner memerlukan akses langsung, sehingga tidak berlaku untuk daftar terhubung (linked list) meskipun daftarnya sudah terurut.
Anda telah memahaminya
- Pencarian linear membandingkan setiap elemen dari awal, bekerja pada semua jenis daftar, dan adalah $O(n)$
- Pencarian biner membutuhkan data yang terurut dengan akses langsung, membandingkan elemen tengah dan mengurangi rentang menjadi setengah setiap kali, memberikan $O(\log_2 n)$: sekitar 20 perbandingan untuk satu juta item
- Jejakkan pencarian biner dengan menunjukkan
low,high,middan nilai pada setiap langkah - Pilih dari data: tidak terurut, kecil, atau daftar terhubung berarti linear; besar, terurut, dan sering dicari berarti biner