Python'da Doğrusal Arama: Örneklerle Başlangıç Rehberi

Arama algoritmalarına geldiğimizde, doğrusal arama en basit olanlardan biridir. Bir listede aradığınızı bulana kadar öğeleri tek tek gözden geçirdiyseniz, aslında doğrusal arama yapmışsınız demektir!

Anlaşılması kolay olmasının yanı sıra, doğrusal arama diğer bazı arama algoritmalarının aksine sıralanmamış verilerde de çalıştığı için kullanışlıdır. Bu esneklik, verilerin sıralanmasının mümkün olmadığı senaryolarda onu iyi bir seçenek yapar. Bu eğitimde Python kullanacağım; başlamadan önce Python'u tazelemek isterseniz, Python Programming beceri yoluna göz atın.

Doğrusal Arama Nedir?

Doğrusal arama, bir listedeki belirli bir değeri, her bir öğeyi tek tek kontrol ederek bulan bir algoritmadır. İlk öğeden başlar, hedefle karşılaştırır ve hedefi bulana ya da listenin sonuna gelene kadar liste boyunca ilerlemeye devam eder. Basit ve sezgisel bir algoritmadır.

Doğrusal arama çalışmak için verilerin sıralı olmasını gerektirmez, bu nedenle esas olarak sıralanmamış veri kümelerinde kullanılır. Bu, sıralamanın pratik olmadığı ya da ham verilerle çalıştığınız durumlarda kullanışlıdır. Ancak bu avantajın bir bedeli vardır: Önceden sıralama gerektiren diğer algoritmalar kadar verimli değildir.

Doğrusal arama, nispeten küçük veri kümeleriyle çalıştığınızda veya verileri sıralamak mümkün olmadığında idealdir. Aşağıdaki diyagram basitleştirilmiş bir açıklama sunar.

Doğrusal Aramayı Seçmek

Avantajlarına ve ayrıca belirgin bir dezavantajına göz atalım: 

Neden Doğrusal Aramayı Seçmeli?

Bana göre doğrusal aramanın üç belirgin faydası var:

Sadelik Öncelikliyse

Doğrusal aramanın en büyük avantajlarından biri sadeliğidir. Algoritma anlaması ve uygulaması kolaydır. Karmaşık sıralamalarla ya da veriyi bölmeyle uğraşmanıza gerek yoktur. Listenin başından başlayın ve aradığınızı bulana kadar her öğeyi kontrol edin.

Sıralamaya Vakit Olmadığında

İkili arama gibi diğer arama algoritmalarının aksine, doğrusal arama veri kümesinin sıralı olmasını gerektirmez. Bu da hızlıca bir şey bulmanız gerektiğinde onu ideal kılar.

Çok Yönlülük Gerektiğinde

Doğrusal aramanın bir diğer artısı da çok yönlü olmasıdır. Yalnızca dizilerle değil, bağlı listeler gibi diğer Python veri yapıları ile de çalışır. Öğelere sıralı olarak erişebildiğiniz sürece doğrusal arama işi görür. Sayılardan dizgelere ve hatta nesnelere kadar farklı veri türlerini işleyebilecek kadar esnektir.

Neden Doğrusal Aramayı İki Kez Düşünmeli?

Dikkate alınması gereken bir konu var:

Verimlilik Önemliyse

Doğrusal aramanın en büyük dezavantajı, özellikle büyük veri kümelerinde verimsizliğidir. Zaman karmaşıklığı O(n)'dir; yani en kötü durumda listedeki her bir öğeyi kontrol etmek zorunda kalabilirsiniz! Binlerce ya da milyonlarca kayıtla çalışıyorsanız bu ciddi bir yavaşlamaya yol açabilir. Ancak küçük veri kümelerinde bu verimsizlik ihmal edilebilir olabilir.

Python'da Doğrusal Arama Algoritması Uygulamak

Python'da doğrusal aramayı yazmanın iki yaygın yolu vardır: yinelemeli yöntem ve özyinelemeli yöntem. Bu iki yöntemi göstermek için önce yinelenmeyen 100 sayıdan oluşan basit bir veri kümesi oluşturalım.

numbers = [12, 7, 19, 3, 15, 25, 8, 10, 42, 56, 77, 23, 89, 65, 33, 99, 14, 2, 37, 81,
           48, 64, 22, 91, 6, 40, 59, 87, 28, 53, 74, 9, 16, 39, 71, 93, 54, 32, 61, 27,
           35, 18, 49, 68, 83, 46, 57, 29, 95, 11, 26, 44, 78, 5, 66, 73, 41, 85, 31, 50,
           20, 63, 88, 34, 90, 60, 67, 4, 52, 36, 62, 80, 21, 84, 98, 13, 45, 69, 30, 38,
           47, 17, 92, 55, 70, 76, 82, 24, 43, 1, 100, 58, 96, 75, 97, 94, 86, 72, 51, 79]Altyapı:

Yinelemeli yöntem

Yinelemeli yaklaşım muhtemelen doğrusal aramayı anlamanın en kolay yoludur. Hedefi bulana veya sona gelene kadar liste boyunca döngü kurarak her öğeyi kontrol edersiniz.

Önce fonksiyonumuzu oluşturacağız:

1. Listede yer alan arr içindeki her öğe üzerinde döngü kuracağız.

2. Her öğeyi hedef ile karşılaştıracağız.

3. Eşleşme bulursak, hedefin bulunduğu indeksi döndürürüz.

4. Döngüyü hedefi bulmadan tamamlarsak, öğenin mevcut olmadığını belirtmek için 1 döndürürüz.

def linear_search_iterative(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # Return the index if the target is found
    return -1  # Return -1 if the target is not foundAltyapı:

Şimdi fonksiyonumuzu veri kümemizde çalıştırıp sonucu yazdıralım:

# Run the function on the numbers list
target = 91
index = linear_search_iterative(numbers, target)

if index != -1:
    print(f"Target {target} found at index {index}")
else:
    print(f"Target {target} not found!")Altyapı:

Bu kodu çalıştırdığımızda, hedef değerin 23. öğede bulunduğunu görürüz.

Özyinelemeli yöntem

Özyinelemeli yöntem, liste içinde arama yapmak için kendini çağıran bir fonksiyon kullanır. Her özyinelemeli çağrı bir seferde bir öğeyi işler ve ardından bir sonrakine geçer. Bu, hedef bulunana veya listenin sonuna gelinene kadar devam eder.

Özyinelemeli fonksiyonumuzu oluşturalım:

1. İlk öğeyi (0. indeks) kontrol ederek başlayacağız.
2. Hedef eşleşirse, indeksi döndüreceğiz.
3. Hedef eşleşmezse, aynı fonksiyonu özyinelemeli olarak çağıracağız ancak bir sonraki öğeyi kontrol etmek için indeksi 1 artıracağız.
4. Özyineleme, hedefi bulana ya da listenin sonuna gelene kadar devam eder.

def linear_search_recursive(arr, target, index=0):
    if index >= len(arr):  # Base case: we've checked all elements
        return -1
    if arr[index] == target:  # Base case: target found
        return index
    return linear_search_recursive(arr, target, index + 1)  # Recursive case: check next elementAltyapı:

Bu fonksiyonu çalıştırmak için yukarıdakiyle aynı kodu kullanabiliriz ve hedefimiz için aynı indeks değerini döndürür: 23.

Unutmayın, bu yaklaşım daha fazla bellek kullanır çünkü her özyinelemeli çağrı çağrı yığınına yeni bir katman ekler. Şuna göz atın: Understanding Recursive Functions in Python özyineleme hakkında daha yakından bilgi için.

Zaman ve Bellek Karmaşıklığı

Bir algoritmanın verimliliğini değerlendirmenin bir yolu, zaman ve bellek karmaşıklığına bakmaktır. Farklı karmaşıklık ölçüm yolları için şu eğitime göz atın: Analyzing Complexity of Code through Python.

Zaman karmaşıklığı

Bir algoritmanın zaman karmaşıklığı, tamamlanması için gereken sürenin girdi boyutu arttıkça nasıl değiştiğini ifade eder. Doğrusal aramanın zaman karmaşıklığı O(n)'dir; burada n listedeki öğe sayısıdır. Bu, en kötü durumda algoritmanın hedefi bulmadan önce her bir öğeyi kontrol etmesi gerekebileceği (ya da hedefin listede olmadığını belirlemek için) anlamına gelir. Bu oldukça verimsizdir, özellikle büyük veri kümeleri için. Bu yüzden doğrusal arama, yalnızca bir kez arama yapmamız gereken daha küçük, sıralanmamış veri kümelerinde en iyi sonucu verir.

Bellek karmaşıklığı

Bir algoritmanın bellek karmaşıklığı, girdi boyutu arttıkça ne kadar bellek gerektirdiğinin bir ölçüsüdür. Doğrusal arama algoritmasının bellek karmaşıklığı, kullandığımız yönteme bağlıdır. Yinelemeli yöntem için bellek karmaşıklığı O(1)'dir; yani algoritma, girdi listesinin boyutundan bağımsız olarak sabit miktarda bellek gerektirir. Bunun nedeni, yinelemeli sürümün girdi listesi ve mevcut indeksi takip etmek için birkaç değişken dışında ek bellek gerektirmemesidir.

Özyinelemeli yöntem için bellek karmaşıklığı O(n)'dir; yani gereken bellek, girdi listesinin boyutuyla doğrusal olarak artar. Bunun nedeni, listedeki her öğe için çağrı yığınına katmanlar ekleyen özyinelemeli fonksiyon çağrılarıdır. Daha büyük bir liste, bu çağrıların saklanması için daha fazla bellek gerektirir ve özyinelemeli yaklaşımı bellek açısından daha az verimli kılar.

Doğrusal Aramanın Gerçek Dünya Uygulamaları

Doğrusal arama büyük veri kümeleri için en verimli algoritma olmayabilir, ancak birçok senaryoda pratik kullanımları vardır. Doğrusal aramanın iş için en iyi araç olduğu bazı durumlara bakalım.

Sıralamanın pratik olmadığı küçük veri kümeleri

Doğrusal arama, sıralamak için harcanacak zaman ya da kaynaklara değmeyecek küçük veri kümeleriyle uğraşırken sıkça başvurduğum yöntemdir. Bu durumlarda, doğrusal aramanın sadeliği, verileri daha karmaşık arama algoritmaları için sıralamanın getireceği ek yüke kıyasla daha verimli olabilir.

Hedefin ilk geçtiği yeri bulmak

Doğrusal aramanın bir diğer yaygın kullanım durumu, bir hedef değerin ilk geçtiği yeri bulmanız gerektiğinde ortaya çıkar. Doğrusal arama liste boyunca birer öğe ilerlediği için doğal olarak hedefin ilk örneğini bulur ve konumunu döndürür. Bu, bir karakterin bir dizgede ilk göründüğü yeri aramak gibi durumlarda özellikle kullanışlıdır.

Asgari kurulum gerektiğinde

Bazen doğrusal aramanın sadeliği onu en iyi seçenek haline getirir. Örneğin, yeniden kullanmayı beklemediğiniz verilerde hızlı bir arama yapıyorsanız ya da hızlıca kabaca bir yanıt gerekiyorsa, doğrusal aramanın asgari kurulumu size zaman kazandırabilir.

Doğrusal Arama ve Diğer Arama Algoritmaları

Doğrusal arama, mevcut birçok arama algoritmasından yalnızca biridir. İki başka yaygın arama algoritmasına bakalım: ikili arama ve karma tablo araması.

Doğrusal arama ve ikili arama

İkili arama, sıralı bir dizide hedef değerin konumunu arama aralığını tekrar tekrar ikiye bölerek bulan bir algoritmadır. Zaman karmaşıklığı O(log n) olup doğrusal aramadan çok daha verimlidir. Ancak yalnızca sıralı verilerde çalışır. Veri kümeniz sıralı olduğunda, her adımda arama alanını yarıya indirdiği için gerekli karşılaştırma sayısını ciddi biçimde azaltır ve neredeyse her zaman daha iyi tercihtir.

Doğrusal arama, veriniz sıralı olmadığında daha uygun olabilir; çünkü doğrusal arama sıralı olsun olmasın her veri kümesinde çalışır. Ancak O(n) zaman karmaşıklığıyla, sıralı veri kümelerinde çok daha az verimlidir.

Doğrusal arama ve karma tablo araması

Karma tablo araması, bir öğeyi hızlıca bulmak için bir karma tablosu kullanan bir yöntemdir. Zaman karmaşıklığı O(1) olup doğrusal ya da ikili aramadan belirgin şekilde hızlıdır. Ancak bu hızın bir bedeli vardır: Önce bir karma tablosu oluşturmanız gerekir; bu da hem zaman hem ek bellek gerektirir. Karma tablo aramaları, başlangıç kurulumunun zamanla karşılığını verdiği, büyük veri kümelerinde çoklu aramalar yapmanız gerektiğinde en iyi sonucu verir.

Buna karşılık, doğrusal arama herhangi bir kurulum gerektirmez ve daha yalın bir seçenektir. Yalnızca bir kez ya da birkaç kez arama yapmanız gerektiğinde, bir karma tablosu kurmanın ek süresi gerekçelendirilemediğinde daha iyi tercihtir. Ayrıca algoritmayı kullanmak için bir karma tablo saklamanız gerekmediğinden, doğrusal arama bellek açısından da daha verimli olabilir.

Yaygın Hatalar ve Nasıl Kaçınılır

Doğrusal arama düz bir algoritma olsa da dikkat edilmesi gereken birkaç yaygın hata vardır.

Yinelemede bir-eksik-bir-fazla hataları

Doğrusal aramayı uygularken en sık yapılan hatalardan biri bir-eksik-bir-fazla hatasıdır. Bu, yinelemeye yanlış indeksten başlamak ya da yanlış yerde bitirmekten kaynaklanır. Python listelerinin sıfırdan indekslendiğini, yani ilk öğenin indeksinin 0 olduğunu unutmamak önemlidir. Bunu unutmak, ilk öğeyi yanlışlıkla atlamanıza ya da bir adım fazla yineleme yapmanıza ve bunun sonucunda hatalı sonuçlara ya da hatalara yol açabilir.

Döndürülen indeksi yanlış anlamak

Bir diğer yaygın sorun, hedef listede bulunamadığında fonksiyonun ne döndürdüğünü yanlış anlamaktır. Geleneksel olarak birçok arama algoritması (doğrusal arama dahil) hedefin bulunmadığını belirtmek için -1 döndürür. Ancak bazı yeni başlayanlar None, False ya da başka bir değer döndürüldüğünü varsayabilir ve bu da sonuçları yorumlarken kafa karışıklığına neden olur.

Doğrusal aramanın kullanılmaması gereken durumlar

Daha önce belirttiğimiz gibi, doğrusal arama daha büyük veri kümelerinde hızla verimsiz hale gelir. Bu nedenle, küçük ve sıralanmamış veri kümeleri ya da hızlı, tek seferlik aramalar için saklanması en iyisidir.

Sonuç

En anlaşılır arama yöntemlerinden biri olan doğrusal arama, bir listedeki her öğeyi sırasıyla kontrol eder; bu da onu anlamayı ve uygulamayı kolaylaştırır. Doğrusal arama, özellikle verilerin sıralı olmadığı küçük veri kümelerinde, hızlı ve tek seferlik aramalar için güvenilir bir seçimdir.

Arama algoritmalarına ilgi duyuyorsanız, bu serideki diğer yazılarıma göz atın: Python'da İkili Arama, Python'da Derinlik Öncelikli Arama ve Python'da Genişlik Öncelikli Arama. Ayrıca daha ileri konular olarak AVL Ağacı: Python Uygulamasıyla Kapsamlı Rehber ve Python'da Ağ Analizine Giriş ilginizi çekebilir.