Doğrusal Arama
- İngilizcesi
- Linear Search
- Türkçe karşılığı
- sıralı arama
- Okunuşu
- liniır sörç
Kısaca
Doğrusal arama (linear search), bir değeri listenin öğelerini baştan tek tek kontrol ederek eşleşme bulana ya da sona ulaşana kadar arar ve O(n) zaman alır.
Doğrusal arama (linear search) nedir?
Var olan en basit aramadır: ilk öğeyi hedefle karşılaştırın, sonra ikinciyi ve böyle devam edin. Hedef 7. konumdaysa 7 karşılaştırma sürer; hiç yoksa her öğe kontrol edilir. Değer listedeyse ortalamada listenin yaklaşık yarısı incelenir; bu da hâlâ O(n), yani listenin uzunluğuyla orantılıdır.
Gücü, veriden hiçbir şey istememesidir. Listenin sıralı ya da indeksli olması gerekmez; yalnızca sırayla okunabilen bağlı listelerde ve akışlarda çalışır ve 30 yaşından büyük ilk kullanıcı gibi herhangi bir koşula göre arayabilir. JavaScript'in indexOf ve find'ı ile Python'un listeler üzerindeki in operatörü gibi yerleşik fonksiyonlar doğrusal arama kullanır.
Küçük koleksiyonlar için doğrusal arama pratikte çoğu zaman en hızlı seçimdir: hiçbir hazırlık yoktur ve birkaç düzine öğeyi art arda taramak CPU önbellekleri için çok uygundur. Yalnızca binary search kullanmak için önce sıralamak, ancak aynı veri birçok kez arandığında karşılığını verir.
Sık yapılan bir yanlış, doğrusal aramanın her zaman kötü bir işaret olduğunu düşünmektir. Bir döngünün içine gizlendiğinde sorun olur; örneğin binlerce öğenin her biri için if item in big_list kontrolü yapmak O(n²)'ye dönüşür. Listeyi, öğeleri ortalamada O(1)'de bulan bir set ya da hash map ile değiştirmek genellikle çözümdür.
Önemli noktalar
- Doğrusal arama, bir eşleşme bulana kadar öğeleri tek tek kontrol eder.
- O(n) zaman alır ve sıralama ya da indeks gerektirmez.
- Bağlı listelerde, akışlarda ve her arama koşulunda çalışır.
- Küçük koleksiyonlarda çoğu zaman en hızlı seçenektir.
- Döngülerin içinde O(n²)'ye dönüşebilir; onun yerine set ya da hash map kullanın.
Örnek
def linear_search(items, target):
for index, value in enumerate(items):
if value == target:
return index # found: stop early
return -1 # checked everything, not there
print(linear_search([7, 3, 9, 4], 9)) # 2
# Slow: a linear search inside a loop → O(n * m)
banned = ["spam@x.com", "bot@y.com"] # imagine thousands of entries
# clean = [u for u in users if u.email not in banned]
# Fast: a set makes each lookup O(1) on average
banned_set = set(banned)
# clean = [u for u in users if u.email not in banned_set]Sık sorulan sorular
Doğrusal arama ile binary search arasındaki fark nedir?
Doğrusal arama öğeleri tek tek kontrol eder ve her listede O(n) zamanda çalışır. Binary search ise sıralı bir listeyi tekrar tekrar ikiye böler ve O(log n) zaman alır, ama verinin önce sıralanmasını gerektirir.
Doğrusal arama ne zaman iyi bir seçimdir?
Küçük ya da sıralanmamış koleksiyonlar, yalnızca sırayla okunabilen veriler, karmaşık koşullu aramalar ya da sıralamanın veya indeks kurmanın daha pahalıya geleceği yalnızca bir kez aranan listeler için.
Doğrusal aramanın zaman karmaşıklığı nedir?
En kötü ve ortalama durumda O(n), çünkü her öğeyi kontrol etmesi gerekebilir. En iyi durum, hedef ilk öğe olduğunda O(1)'dir.
İlgili sayfalar
- İkili AramaVeri Yapıları, s. 21İkili arama, sıralı bir listedeki bir değeri arama aralığını sürekli yarıya bölerek bulan bir algoritmadır; her öğeyi denetlemek yerine O(log n) sürer.
- DiziProgramlamanın Temelleri, s. 15Dizi, tek bir ad altında saklanan ve her öğesine genellikle 0'dan başlayan indeks adlı sayısal konumuyla erişilen, sıralı bir değerler koleksiyonudur.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- Hash TablosuVeri Yapıları, s. 18Hash tablosu, anahtar-değer çiftlerini saklayan ve hash fonksiyonuyla herhangi bir anahtarın değerini ortalamada sabit sürede bulan bir veri yapısıdır.
- SetVeri Yapıları, s. 29Set, her farklı değeri en fazla bir kez saklayan ve bir değerin içinde olup olmadığını çoğunlukla sabit sürede kontrol edebilen bir koleksiyondur.
- AlgoritmaProgramlamanın Temelleri, s. 1Algoritma, bir listeyi sıralamak ya da en kısa yolu bulmak gibi bir sorunu çözmek veya bir işi tamamlamak için izlenen, sonlu ve adım adım yönergeler bütünüdür.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin