Doğrusal Arama Nedir?
İngilizce: Linear Search
Yayın: · Son güncelleme:
Doğrusal Arama Nedir? Kısaca
Doğrusal arama (linear search), bir listedeki elemanları baştan başlayarak tek tek kontrol eden ve aranan değeri bulduğunda duran en basit arama yöntemidir. Liste sıralı olmasa da çalışır.
Doğrusal arama nedir?
Doğrusal arama, bir listede aradığınız değeri ilk elemandan başlayıp sırayla kontrol ederek bulma yöntemidir. Eleman bulunduğunda arama durur ve konumu döndürülür. Listenin sonuna gelindiği hâlde değer bulunamazsa sonuç "yok" olur. Sıralı arama olarak da adlandırılır.
Nasıl çalışır?
Bir çekmecede anahtarınızı aradığınızı düşünün. Eşyaları tek tek eline alıp bakarsınız; anahtarı bulduğunuz anda durursunuz. Doğrusal arama da bu mantıkla çalışır.
Kodda bunun karşılığı tek bir döngüdür. Örneğin [12, 7, 31, 5, 18] listesinde 5 değerini arayalım. Algoritma 12'ye, 7'ye ve 31'e bakar, dördüncü adımda 5'i bulur ve 3 numaralı konumu döndürür. Aradığınız 40 olsaydı, beş elemanın hepsi kontrol edilir ve "bulunamadı" sonucu verilirdi.
Avantajları ve sınırları
En büyük avantajı basitliğidir. Listenin sıralı olması gerekmez ve neredeyse her veri yapısında uygulanabilir. Küçük listelerde, örneğin 20-30 elemanlık bir menü listesinde, daha karmaşık yöntemlere hiç gerek yoktur.
Sorun veri büyüdüğünde başlar. Bir milyon elemanlı bir listede aranan değer sonda ise bir milyon karşılaştırma yapılır. Aynı liste sıralı olsaydı ikili arama bu işi 20 civarı adımda bitirirdi. Uygulamanızda aynı listede sürekli arama yapıyorsanız, veriyi bir kez sıralamak ya da bir sözlük yapısına aktarmak çoğu zaman büyük kazanç sağlar. Python'daki in operatörü ve JavaScript'teki indexOf listelerde arka planda doğrusal arama yapar.
Sıkça Sorulan Sorular
Doğrusal aramanın zaman karmaşıklığı nedir?
O(n) olarak ifade edilir. Liste iki katına çıkarsa en kötü durumda gereken adım sayısı da iki katına çıkar.
Doğrusal arama ne zaman tercih edilir?
Liste küçükse, sıralı değilse ya da yalnızca bir kez arama yapılacaksa doğrusal arama yeterlidir. Büyük ve sık aranan verilerde ise sıralayıp ikili arama yapmak ya da hash tablosu kullanmak daha verimlidir.