Doğrusal arama ve arama kalıpları

Bir veride belli bir değeri ya da bir koşula uyan kaydı bulmak, programlarda en sık yapılan işlerden biridir. En basit yol, elemanlara baştan sona sırayla bakmaktır. Bu yönteme doğrusal arama (linear search) denir.

Bu hafta “bir değer var mı?” sorusuyla kalmayacağız. İlk eşleşme, tüm eşleşmeler, bulunamama, sıralı veride erken durma, minimum/maksimum ve koşula göre arama gibi başka arama kalıplarını da inceleyeceğiz.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

  • Doğrusal aramanın nasıl çalıştığını açıklayabilmeli,
  • İlk eşleşmeyi ve tüm eşleşmeleri bulabilmeli,
  • Değer bulunamadığında fonksiyonun ne döndüreceğini açıkça belirleyebilmeli,
  • Sıralı veride doğrusal aramanın hangi durumda erken durabileceğini açıklayabilmeli,
  • Erken durmanın, en kötü durumdaki O(n) maliyetini neden değiştirmediğini açıklayabilmeli,
  • Koşula göre kayıt araması yapabilmeli,
  • Minimum/maksimum bulma kalıbını uygulayabilmeli,
  • Aramanın en kötü durumda neden O(n) olduğunu sezgisel olarak açıklayabilmeli,
  • Boş liste ve tek elemanlı liste gibi uç durumları (edge case) test edebilmelisiniz.

2 Doğrusal arama nasıl çalışır?

Listedeki elemanları sırayla aranan değerle karşılaştırırız:

[14, 7, 23, 9, 18]
          ↑
       aranan 23

Kontroller:

  1. 14 == 23 → hayır
  2. 7 == 23 → hayır
  3. 23 == 23 → evet, bulundu

break, ilk eşleşme bulununca döngüyü bitirir; kalan elemanlara boşuna bakılmaz.

3 Fonksiyona dönüştürelim

Fonksiyonun sözleşmesi, yani ne döndüreceğine dair verdiği söz, burada açık:

  • Bulunursa indeks,
  • Bulunamazsa -1.

Başka bir tasarım, değer bulunamayınca None döndürebilir. Önemli olan, bu durumda ne döneceğinin önceden belirlenmiş olması ve her seferinde aynı olması.

4 Kaç karşılaştırma yapıldı?

Aramanın maliyetini görmek için bir sayaç ekleyelim:

Aranan değer ilk sıradaysa bir kontrol yeterlidir. Son sıradaysa ya da hiç yoksa bütün listeyi dolaşmak gerekebilir.

5 O(n) sezgisi

Liste iki kat büyüdüğünde en kötü durumda yapılması gereken karşılaştırma sayısı da yaklaşık iki kat büyür.

flowchart LR
    A["n eleman"] --> B["en kötü durumda n kontrol"]
    C["2n eleman"] --> D["en kötü durumda 2n kontrol"]

Bu yüzden doğrusal aramanın maliyetine O(n) deriz.

6 Sıralı veride doğrusal arama: erken durabilir miyiz?

Doğrusal aramayı sıralı veride de kullanabiliriz. Veri küçükten büyüğe sıralıysa, hedefi geçtiğimiz anda aramayı bırakabiliriz.

Örneğin 13 değerini şu listede arayalım:

[3, 5, 8, 11, 14, 20]
                ↑
              14 > 13

14’e geldiğimizde ileride 13 olamayacağını biliriz, çünkü sonraki değerler daha da büyüktür.

6.1 Erken durma neden yine O(n)?

Verinin sıralı olduğunu bilmek, bazı başarısız aramalarda erken durmamızı sağlar. Ama şu hedefi düşünün:

[3, 5, 8, 11, 14, 20, 27, 35]
                                ↑
                               35

Son elemanı bulmak için yine bütün elemanlara bakmak gerekebilir. Hedef bütün değerlerden büyükse de listenin sonuna kadar ilerleriz.

Bu yüzden sıralı veride de doğrusal arama en kötü durumda O(n)’dir.

Important

Bir iyileştirme bazı girdilerde işi azaltabilir, ama en kötü durumdaki büyümeyi kendiliğinden değiştirmez.

7 Tahmin et: kaç kontrol yapılır?

Aşağıdaki kodu çalıştırmadan önce 13, 14 ve 100 hedefleri için kaç kontrol yapılacağını tahmin edin:

Gelecek hafta ikili aramaya geçerken şu soruyu soracağız:

Sıralı olma bilgisini yalnızca erken durmak için değil, arama alanını çok daha hızlı küçültmek için kullanabilir miyiz?

8 Alıştırma: ilk eşleşme

Aşağıdaki fonksiyonu, listedeki ilk negatif sayının indeksini döndürecek biçimde tamamlayın. Negatif sayı yoksa fonksiyon -1 döndürsün.

for i in range(len(values)): ve if values[i] < 0: return i kalıbını kullanabilirsiniz.

def first_negative(values):
    for i in range(len(values)):
        if values[i] < 0:
            return i
    return -1

9 Alıştırma: sıralı doğrusal aramada erken dur

Aşağıdaki fonksiyonu tamamlayın: veri sıralı olduğu için, hedef geçildiği anda fonksiyon -1 döndürsün.

Eşitlik kontrolünden sonra if value > target: return -1 ekleyin.

def ordered_search(values, target):
    for i, value in enumerate(values):
        if value == target:
            return i
        if value > target:
            return -1
    return -1

10 İlk eşleşme mi, tüm eşleşmeler mi?

İlk eşleşmeyi arıyorsak bulunca dururuz:

if condition:
    return item

Tüm eşleşmeleri arıyorsak listenin sonuna kadar devam ederiz:

Bu fark performansı da etkiler: ilk eşleşme erken bitebilir, tüm eşleşmeleri bulmak için ise bütün veriye bakmak gerekir.

11 Kayıt listesinde arama

Burada None kaydın bulunamadığını gösterir. Sonucu kullanmadan önce None olup olmadığına bakmalıyız:

student = find_student(students, 999)
if student is None:
    print("Öğrenci bulunamadı")
else:
    print(student["name"])

12 Aynı aramayı çok kez yapacaksak?

Numaraya göre tek bir arama yapacaksak listeyi dolaşmak yeterli olabilir. Ama binlerce kayıtta aynı aramayı çok sık yapacaksak veriyi baştan farklı düzenlemek daha uygun olabilir:

students_by_number = {
    101: {"name": "Ayşe", "grade": 80},
    102: {"name": "Bora", "grade": 67},
    103: {"name": "Cem", "grade": 91},
}

Önceki haftalarda gördüğümüz fikir burada yine karşımıza çıkıyor:

Algoritmayı seçmek kadar veriyi nasıl düzenlediğimiz de önemlidir.

13 Minimum bulma kalıbı

En küçük değeri bulmak da bir tür aramadır. Python’da hazır min() fonksiyonu var, ama algoritmayı adım adım görmek için kendimiz yazalım:

Başlangıç değeri olarak neden 0 kullanmadık? Şu listeye bakın:

[12, 5, 18]

smallest = 0 ile başlarsak listedeki hiçbir değer 0’dan küçük olmadığı için fonksiyon 0 döndürür. Oysa 0 listede yok, doğru cevap 5. Başlangıç değerini listenin içinden seçmek daha güvenlidir.

14 Kayıtlarda minimum/maksimum

En yüksek notlu öğrenciyi bulalım:

15 Uç durumlar

Bir arama fonksiyonunu yalnızca “normal” veriyle test etmeyin. En az şu durumları düşünün:

  • Boş liste,
  • Tek elemanlı liste,
  • Hedef ilk sırada,
  • Hedef son sırada,
  • Hedef yok,
  • Birden çok eşleşme,
  • Tekrar eden değerler.

16 Bölüm özeti

  • Doğrusal arama elemanları sırayla kontrol eder.
  • İlk eşleşme bulununca arama erken bitebilir.
  • Tüm eşleşmeleri bulmak için bütün veri dolaşılır.
  • Veri sıralıysa bazı başarısız aramaları, hedefi geçtiğimiz anda bitirebiliriz.
  • Erken durmaya rağmen doğrusal arama en kötü durumda yine O(n)’dir.
  • Değer bulunamayınca ne döneceği (-1 ya da None) önceden açıkça belirlenmelidir.
  • Minimum/maksimum bulma da doğrusal dolaşma kalıbına dayanır.
  • Aynı tür arama çok sık yapılıyorsa veriyi sözlük gibi başka bir yapıda tutmak daha uygun olabilir.

17 Kendinizi kontrol edin

  1. Doğrusal arama neden en kötü durumda O(n)’dir?
  2. Sıralı doğrusal arama hangi durumda normal doğrusal aramadan erken durabilir?
  3. Erken durmak, en kötü durumdaki O(n) maliyetini neden değiştirmez?
  4. İlk eşleşmeyi aramakla tüm eşleşmeleri aramak arasında algoritma açısından ne fark var?
  5. “Bulunamadı” durumunu neden açıkça tasarlamak gerekir?
  6. Minimum bulurken neden başlangıç değeri olarak her zaman 0 kullanmamalıyız?
  7. Aynı anahtara göre çok sık arama yapılıyorsa veri yapısı seçimi nasıl değişebilir?
Back to top