Algoritma Pencarian
| English | Bahasa Indonesia |
|---|---|
| Searching/ˈsɜːtʃɪŋ/ | Pencarian |
| linear search/ˈlɪnɪə sɜːtʃ/ | pencarian linear |
| binary search/ˈbaɪnəri sɜːtʃ/ | pencarian biner |
| sorted/ˈsɔːtɪd/ | diurutkan |
Menemukan nilai
- Mencari berarti menemukan nilai target dalam kumpulan data.
- Dua algoritma standar: pencarian linear dan pencarian biner.
- Keduanya mengembalikan indeks di mana target berada — atau sinyal "tidak ditemukan" (sering
-1). - Mana yang boleh Anda gunakan bergantung pada apakah data tersebut terurut.
Pencarian linear
- Periksa setiap elemen dari awal, satu per satu, hingga Anda menemukan target.
for (int i = 0; i < a.length; i++) if (a[i] == target) return i;- Bekerja pada apapun array — terurut atau tidak.
- Kasus terburuk: ia memeriksa setiap elemen (
npemeriksaan).
Pencarian biner
- Membutuhkan array terurut. Periksa elemen tengah setiap kali.
- Jika tengah adalah target, selesai. Jika target lebih kecil, cari setengah kiri; jika lebih besar, setengah kanan.
- Setiap langkah memotong setengah rentang yang tersisa untuk dicari.
- Jauh lebih cepat pada array besar terurut — sekitar
log₂ npemeriksaan, bukann.
Mengapa pencarian biner cepat
- Pencarian linear dari satu juta item: hingga satu juta pemeriksaan.
- Pencarian biner dari satu juta item terurut: sekitar 20 pemeriksaan.
- Hal penting: array harus sudah terurut.
- Memotong berulang-ulang adalah ide besar di balik
O(log n).
Pencarian biner hanya bekerja pada array TERURUT — menjalankannya pada data tak terurut memberikan jawaban salah. Ia juga membandingkan dengan tengah dan membuang setengah rentang setiap langkah; pencarian linear membandingkan dari awal dan hanya membuang satu elemen. Jika Anda tidak yakin datanya terurut, Anda harus menggunakan pencarian linear (atau urutkan terlebih dahulu).
Pencarian biner untuk 7 dalam [1, 3, 5, 7, 9]:
- Tengah adalah
5(indeks 2). 7 > 5, jadi cari setengah kanan. - Setengah kanan adalah
[7, 9]; tengah adalah7. Ditemukan pada indeks 3. - Dua pemeriksaan alih-alih empat — rentangnya dipotong setengah setiap kali.
Pencarian linear memeriksa elemen dari awal (bekerja pada array apa pun, hingga n pemeriksaan). Pencarian biner memerlukan array terurut, membandingkan dengan tengah, dan memotong setengah rentang pencarian setiap langkah (sekitar log₂ n pemeriksaan). Keduanya mengembalikan indeks yang ditemukan, atau sinyal "tidak ditemukan" seperti -1.
Pencarian linear vs pencarian biner
Pencarian biner membagi dua rentang yang sudah terurut setiap langkahnya.
Pencarian linear...
Linear = dari awal hingga akhir; bekerja pada array apa pun.
Pencarian biner memerlukan array agar...
Pencarian biner hanya bekerja pada data yang terurut.
Setiap langkah pencarian biner...
Ia membandingkan dengan nilai tengah dan menyimpan salah satu bagian.
Pencarian biner dalam [1,3,5,7,9] untuk 7: berapa banyak perbandingan (nilai tengah setiap kali)?
Bandingkan dengan 5, lalu dengan 7 — dua perbandingan.
Pencarian biner memberikan hasil yang benar pada array TIDAK TERURUT.
Ia bergantung pada urutan; data tidak terurut akan mengacaukannya.
Cocokkan setiap pencarian dengan sifatnya.
Linear bersifat umum tetapi lebih lambat; biner cepat tetapi memerlukan urutan.