Algoritma Pencarian
Diperkenalkan| English | Makna |
|---|---|
| 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/ | terurut |
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 linear memeriksa setiap elemen secara berurutan hingga target ditemukan

Pencarian biner membagi dua rentang pada setiap langkah
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...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Linear = dari awal hingga akhir; bekerja pada array apa pun.
Pencarian biner memerlukan array agar...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Pencarian biner hanya bekerja pada data yang terurut.
Setiap langkah pencarian biner...
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
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)?
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
Bandingkan dengan 5, lalu dengan 7 — dua perbandingan.
Pencarian biner memberikan hasil yang benar pada array TIDAK TERURUT.
Kesulitan 1/5 · 100 koin + bonus kecil pada penyelesaian pertama hari ini
Ia bergantung pada urutan; data tidak terurut akan mengacaukannya.
Cocokkan setiap pencarian dengan sifatnya.
Kesulitan 2/5 · 140 koin + bonus kecil pada penyelesaian pertama hari ini
Linear bersifat umum tetapi lebih lambat; biner cepat tetapi memerlukan urutan.