- Target
- Dibandingkan
- Tersisih
- Ditemukan
Pencarian linear
Pencarian linear adalah cara paling sederhana untuk menemukan nilai: mulai dari awal dan periksa setiap nilai bergiliran sampai nilai itu ketemu. Cara ini bekerja pada daftar apa pun, terurut atau tidak. Pilih nilai yang dicari, putar pencariannya atau jalankan satu perbandingan setiap kali, dan lihat bagaimana biayanya bergantung pada letak nilai itu, atau apakah nilai itu ada sama sekali. Tekan Putar untuk melihat pencarian, atau Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja. Garis putus-putus menandai nilai yang dicari. Pilih nilainya, jumlah batang, urutan awalnya, atau ketik angka sendiri. Matikan Berhenti di kecocokan pertama untuk menemukan semua kecocokan. Saat papan dipilih, tombol panah melangkah, spasi memutar dan menjeda, serta Home dan End melompat ke awal dan akhir.
Cara kerjanya
- Pilih nilai yang dicari, jumlah batang, dan urutan awalnya. Atau ketik angka sendiri.
- Tekan Putar, atau gunakan Langkah dan Mundur untuk maju satu perbandingan setiap kali. Geser penggeser langkah untuk melompat ke mana saja dalam pencarian.
- Matikan Berhenti di kecocokan pertama untuk memeriksa setiap nilai dan menemukan semua kecocokan.
Cara kerja pencarian linear
Bandingkan nilai pertama dengan target. Jika sama, selesai. Jika tidak, lanjut ke nilai kedua, lalu ketiga, dan seterusnya. Jika sampai di akhir daftar tanpa kecocokan, target tidak ada di daftar. Tidak ada yang perlu disiapkan: daftar tidak perlu terurut.
Berapa banyak perbandingan
Nilai di posisi k ditemukan setelah k perbandingan. Kasus terbaik adalah satu perbandingan, saat target ada di posisi pertama. Kasus terburuk adalah n, saat target ada di posisi terakhir atau tidak ada, karena hanya setelah memeriksa setiap nilai Anda bisa yakin target tidak ada. Rata-rata, untuk nilai yang ada di daftar, dibutuhkan sekitar (n + 1)/2. Untuk daftar terurut, pencarian biner jauh lebih baik: sekitar log₂ n perbandingan, 6 alih-alih hingga 40 untuk 40 nilai.
Pertanyaan yang sering diajukan
Bagaimana cara kerja pencarian linear?
Pencarian ini memeriksa nilai dalam daftar satu per satu, dari yang pertama sampai yang terakhir, hingga menemukan target atau nilainya habis. Pencarian ini juga disebut pencarian sekuensial.
Berapa kompleksitas waktu pencarian linear?
O(n): dalam kasus terburuk, saat target ada di posisi terakhir atau tidak ada, target dibandingkan dengan semua n nilai. Rata-rata, untuk target yang ada di daftar, dibutuhkan sekitar (n + 1)/2 perbandingan.
Kapan pencarian linear menjadi pilihan yang baik?
Untuk daftar pendek, untuk daftar yang tidak terurut dan hanya dicari sekali atau dua kali, dan untuk data yang hanya bisa dibaca berurutan, seperti stream. Mengurutkan dulu agar bisa memakai pencarian biner hanya sepadan jika Anda mencari berkali-kali.
Mengapa nilai yang tidak ada paling mahal?
Karena tidak ada yang memberi tahu pencarian linear untuk berhenti lebih awal. Kecocokan hanya bisa dipastikan tidak ada dengan memeriksa setiap nilai, jadi nilai yang tidak ada di daftar selalu butuh n perbandingan.
Apakah angka saya dikirim ke suatu tempat?
Tidak. Pencarian berjalan di browser Anda, dan pengaturan terakhir Anda tetap tersimpan di penyimpanan lokal browser ini.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor