Doğrusal arama
Doğrusal arama, sıralanmamış bir listede bir isim ararken yaptığınız şeydir: en üstten başlar ve bulana kadar aşağı doğru okursunuz. Var olan en basit aramadır, her listede çalışır ve kısa listeler için çoğu zaman yeterlidir.
Fikir
Hedefi listenin ilk değeriyle karşılaştırın. Eşitlerse durun: hedef 1. sıradadır. Değilse ikinci değerle, sonra üçüncüyle karşılaştırın ve böyle devam edin. Son değer de eşleşmezse hedef listede yoktur. Liste hakkında önceden hiçbir şey bilinmesi gerekmez: sıralı olması gerekmez ve değerler eşitlik açısından karşılaştırılabilen her şey olabilir.
Bir örnek
5, 1, 4, 2, 8 listesinde 4'ü arayın. 5, 4'e eşit mi? Hayır. Ya 1? Hayır. Ya 4? Evet: 3 karşılaştırmadan sonra 3. sırada bulundu. Şimdi aynı listede 7'yi arayın. Beş değerin her biri kontrol edilir ve hiçbiri eşleşmez; bu yüzden 5 karşılaştırmadan sonra yanıt, 7'nin listede olmadığıdır.
Kaç karşılaştırma
Bir değer k. sıradaysa onu bulmak k karşılaştırma gerektirir. Hedefin her sırada olma olasılığı eşitse bu, ortalama (n + 1)/2 karşılaştırma eder: 40 değer için 20,5. Listede olmayan bir değer her zaman n karşılaştırma gerektirir; çünkü ancak son karşılaştırmadan sonra hiçbir değerin eşleşmediği kesinleşir. Yani maliyet listenin uzunluğuyla orantılı olarak artar; bu, O(n) olarak yazılır.
Daha hızlı arama düzen ister
Doğrusal arama hiçbir şeyi atlayamaz, çünkü sıralanmamış bir listede herhangi bir değer herhangi bir yerde olabilir. Liste sıralandığında bir karşılaştırma eşit olup olmadığından fazlasını söyler: hedefin hangi tarafta olduğunu da söyler. İkili arama bunu her adımda listeyi ikiye bölmek için kullanır ve yaklaşık log₂ n karşılaştırma gerektirir; 40 değer için en fazla 6. Ancak sıralamak da zaman alır; bu yüzden yalnızca bir kez aranacak bir liste için doğrusal arama çoğu zaman daha iyi bir seçimdir.
Küçük iyileştirmeler
Nöbetçili sürüm, aramadan önce hedefi listenin sonuna koyar; böylece döngü yalnızca eşleşmeyi test eder, listenin sonunu ayrıca test etmesi gerekmez. Bir değeri her bulunduğunda bir sıra öne veya en başa taşımak, sık aranan değerleri zamanla daha ucuz hale getirir. Hiçbiri n karşılaştırmalık en kötü durumu değiştirmez.
Keşfedin
Uygulamayı açın, Aranan değer alanında bir değer seçin ve Adım'a basın. Kesikli çizgi hedefin yüksekliğini gösterir, her değer kontrol edilirken vurgulanır ve elendiğinde solar, bir eşleşme de yeşile döner. Tam bir geçişi görmek için listede olmayan bir değeri arayın ya da İlk eşleşmede dur seçeneğini kapatıp birkaç eşleşme bulmak için az farklı değer kullanın.
Sık sorulan sorular
Doğrusal aramanın zaman karmaşıklığı nedir?
En kötü ve ortalama durumda O(n), hedef ilk değer olduğunda en iyi durumda O(1). Ek bellek gerektirmez.
Doğrusal arama ile ikili arama arasındaki fark nedir?
Doğrusal arama her değeri sırayla kontrol eder ve her listede çalışır. İkili arama yalnızca sıralı bir listede çalışır, ancak her adımda hedefi içerebilecek kısmı ikiye böler; bu yüzden en fazla n yerine yaklaşık log₂ n karşılaştırma gerektirir.
Doğrusal arama sıralı bir liste gerektirir mi?
Hayır. Bu, en büyük avantajıdır. Sıralı bir listede hedefin olması gereken yeri geçer geçmez durabilir, ama yine de ikili aramadan yavaştır.
Doğrusal arama nerede kullanılır?
Listelerin kısa veya sıralanmamış olduğu her yerde: küçük bir dizide bir öğe bulmak, yalnızca sırayla okunabilen bir dosyayı veya akışı taramak ya da her öğeyi bir koşula göre kontrol etmek. JavaScript'teki indexOf ve Python'daki list.index gibi birçok kütüphane fonksiyonu doğrusal aramadır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Doğrusal aramayı deneyin