Pencarian linear
Pencarian linear adalah yang Anda lakukan saat mencari nama di daftar yang tidak terurut: mulai dari atas dan baca ke bawah sampai ketemu. Ini adalah pencarian paling sederhana, bekerja pada daftar apa pun, dan untuk daftar pendek sering kali sudah cukup.
Idenya
Bandingkan target dengan nilai pertama dalam daftar. Jika sama, berhenti: target ada di posisi 1. Jika tidak, bandingkan dengan nilai kedua, lalu ketiga, dan seterusnya. Jika nilai terakhir juga tidak cocok, target tidak ada di daftar. Tidak ada yang perlu diketahui tentang daftar sebelumnya: daftar tidak harus terurut, dan nilainya boleh apa saja yang bisa dibandingkan kesamaannya.
Contoh
Cari 4 dalam 5, 1, 4, 2, 8. Apakah 5 sama dengan 4? Tidak. 1? Tidak. 4? Ya: ditemukan di posisi 3 setelah 3 perbandingan. Sekarang cari 7 dalam daftar yang sama. Kelima nilai diperiksa dan tidak ada yang cocok, jadi setelah 5 perbandingan jawabannya adalah 7 tidak ada.
Berapa banyak perbandingan
Nilai di posisi k butuh k perbandingan untuk ditemukan. Jika target sama mungkinnya berada di posisi mana pun, rata-ratanya (n + 1)/2 perbandingan: 20,5 untuk 40 nilai. Nilai yang tidak ada selalu butuh n, karena baru setelah perbandingan terakhir dapat dipastikan tidak ada nilai yang cocok. Jadi biayanya tumbuh sebanding dengan panjang daftar, yang ditulis O(n).
Pencarian yang lebih cepat butuh urutan
Pencarian linear tidak bisa melewatkan apa pun, karena dalam daftar tidak terurut nilai apa pun bisa berada di mana saja. Begitu daftar terurut, satu perbandingan memberi tahu lebih dari sama atau tidak: ia memberi tahu di sisi mana target berada. Pencarian biner memanfaatkan itu untuk membagi dua daftar di setiap langkah dan butuh sekitar log₂ n perbandingan, paling banyak 6 untuk 40 nilai. Namun, mengurutkan juga butuh waktu, jadi untuk daftar yang hanya dicari sekali, pencarian linear sering kali pilihan yang lebih baik.
Perbaikan kecil
Versi sentinel menaruh target di akhir daftar sebelum mencari, sehingga perulangan hanya perlu menguji kecocokan, tidak juga akhir daftar. Memindahkan nilai satu tempat ke depan, atau ke paling depan, setiap kali ditemukan membuat nilai yang sering dicari makin murah seiring waktu. Keduanya tidak mengubah kasus terburuk n perbandingan.
Jelajahi
Buka aplikasinya, pilih nilai di Cari, lalu tekan Langkah. Garis putus-putus menunjukkan ketinggian target, setiap nilai disorot saat diperiksa dan memudar setelah tersisih, dan kecocokan berubah hijau. Cari nilai yang tidak ada di daftar untuk melihat satu putaran penuh, atau matikan Berhenti di kecocokan pertama dan gunakan sedikit nilai unik untuk menemukan beberapa kecocokan.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu pencarian linear?
O(n) dalam kasus terburuk dan rata-rata, dan O(1) dalam kasus terbaik, saat target adalah nilai pertama. Pencarian ini tidak butuh memori tambahan.
Apa bedanya pencarian linear dan pencarian biner?
Pencarian linear memeriksa setiap nilai secara berurutan dan bekerja pada daftar apa pun. Pencarian biner hanya bekerja pada daftar terurut, tetapi membagi dua bagian yang mungkin memuat target di setiap langkah, sehingga butuh sekitar log₂ n perbandingan, bukan hingga n.
Apakah pencarian linear butuh daftar terurut?
Tidak. Itulah keunggulan utamanya. Pada daftar terurut, pencarian bisa berhenti begitu melewati posisi tempat target seharusnya berada, tetapi tetap lebih lambat daripada pencarian biner.
Di mana pencarian linear digunakan?
Di mana pun daftar pendek atau tidak terurut: mencari item dalam array kecil, memindai file atau stream yang hanya bisa dibaca berurutan, atau memeriksa setiap elemen terhadap suatu syarat. Banyak fungsi pustaka, seperti indexOf di JavaScript dan list.index di Python, adalah pencarian linear.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba pencarian linear