Doğrusal arama ve arama kalıpları

Bir veri kümesinde belirli bir değeri ya da belirli koşulu sağlayan kaydı bulmak, programlamanın en yaygın görevlerinden biridir. En temel yaklaşım, elemanları baştan sona sırayla kontrol etmektir. Bu yönteme doğrusal arama (linear search) denir.

Bu hafta yalnızca “bir değer var mı?” sorusuna değil; ilk eşleşme, tüm eşleşmeler, bulunamama, sıralı veride erken durma, minimum/maksimum ve koşula göre arama gibi farklı arama kalıplarına odaklanacağız.

1 Bu hafta neleri yapabilmelisiniz?

Bölümün sonunda:

• doğrusal aramanın çalışma mantığını açıklayabilmeli,
• ilk eşleşmeyi ve tüm eşleşmeleri bulabilmeli,
• bulunamama durumunu açıkça yönetebilmeli,
• sıralı veride doğrusal aramanın hangi durumda erken durabileceğini açıklayabilmeli,
• erken durmanın en kötü durum karmaşıklığını neden O(n)’den değiştirmediğini gerekçelendirebilmeli,
• 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 sınır durumlarını test edebilmelisiniz.

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

Bir listedeki değeri sırayla kontrol ederiz:

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

Kontroller:

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

#| edit: false
#| completion: false
numbers = [14, 7, 23, 9, 18]
target = 23

found_index = -1

for i in range(len(numbers)):
    if numbers[i] == target:
        found_index = i
        break

print("İndeks:", found_index)

break, ilk eşleşmeyi bulduktan sonra gereksiz kontrolleri durdurur.

3 Fonksiyona dönüştürelim

#| edit: false
#| completion: false
def linear_search(values, target):
    for i in range(len(values)):
        if values[i] == target:
            return i
    return -1

print(linear_search([10, 20, 30], 20))
print(linear_search([10, 20, 30], 99))

Burada sözleşme nettir:

• bulunursa indeks,
• bulunamazsa -1.

Başka bir tasarım None döndürebilir. Önemli olan, bulunamama durumunun önceden belirlenmiş ve tutarlı olmasıdır.

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

Aramanın maliyetini görünür kılmak için sayaç ekleyelim:

#| edit: false
#| completion: false
def linear_search_with_count(values, target):
    checks = 0

    for i in range(len(values)):
        checks += 1
        if values[i] == target:
            return i, checks

    return -1, checks

values = [4, 8, 12, 16, 20, 24]

for target in [4, 16, 24, 99]:
    index, checks = linear_search_with_count(values, target)
    print(target, "-> indeks:", index, "kontrol:", checks)

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 nedenle doğrusal aramayı O(n) maliyet sezgisiyle ilişkilendiririz.

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

Doğrusal arama yalnızca sırasız veride kullanılmaz. Veri artan biçimde sıralıysa, hedefi geçtikten sonra aramayı bırakabiliriz.

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

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

14 değerine ulaştığımızda artık ileride 13 bulunamayacağını biliyoruz. Çünkü sonraki değerler daha da büyük olacaktır.

#| edit: false
#| completion: false
def ordered_linear_search(values, target):
    checks = 0

    for i, value in enumerate(values):
        checks += 1

        if value == target:
            return i, checks
        if value > target:
            return -1, checks

    return -1, checks

values = [3, 5, 8, 11, 14, 20, 27, 35]

for target in [3, 13, 35, 99]:
    print(target, "->", ordered_linear_search(values, target))

6.1 Erken durma neden yine O(n)?

Sıralı olma bilgisi bazı başarısız aramalarda daha erken durmamızı sağlayabilir. Ancak ş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 nedenle sıralı doğrusal aramanın en kötü durum büyümesi yine O(n) olur.

Important

Bir optimizasyon bazı girdilerde daha az iş yapabilir; bu, en kötü durum büyüme sınıfını otomatik olarak 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:

#| edit: false
#| completion: false
values = [2, 4, 6, 8, 10, 12, 14, 16]

for target in [13, 14, 100]:
    index, checks = ordered_linear_search(values, target)
    print(target, "-> indeks:", index, "kontrol:", checks)

Bu etkinlik, bir sonraki haftada ikili aramaya geçerken şu soruyu hazırlar:

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 fonksiyon, verilen listedeki ilk negatif sayının indeksini döndürmelidir. Negatif sayı yoksa -1 döndürün.

#| exercise: hafta07-first-negative
#| completion: false
#| persist: true
def first_negative(values):
    # Burayı tamamlayın.
    pass

print(first_negative([5, 8, -2, 7, -9]))

#| exercise: hafta07-first-negative
#| check: true
scope = {}
try:
    exec(user_code, scope)
    fn = scope.get("first_negative")
    correct = (
        callable(fn)
        and fn([5, 8, -2, 7, -9]) == 2
        and fn([1, 2, 3]) == -1
        and fn([-1]) == 0
        and fn([]) == -1
    )
except Exception:
    correct = False

feedback = (
    {"correct": True, "message": "İlk negatif değerin indeksi doğru bulunuyor."}
    if correct
    else {"correct": False, "message": "İndeksleri dolaşın; ilk values[i] < 0 durumunda hemen i döndürün. Döngü biterse -1 döndürün."}
)
feedback

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

Solution.

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, veri sıralı olduğu için hedefi geçtiğinde hemen -1 döndürecek biçimde tamamlayın.

#| exercise: hafta07-ordered-search
#| completion: false
#| persist: true
def ordered_search(values, target):
    for i, value in enumerate(values):
        if value == target:
            return i
        # Buraya erken durma koşulunu ekleyin.

    return -1

print(ordered_search([4, 8, 12, 16, 20], 15))

#| exercise: hafta07-ordered-search
#| check: true
scope = {}
try:
    exec(user_code, scope)
    fn = scope.get("ordered_search")
    correct = (
        callable(fn)
        and fn([4, 8, 12, 16, 20], 12) == 2
        and fn([4, 8, 12, 16, 20], 15) == -1
        and fn([], 1) == -1
        and fn([4, 8, 12], 2) == -1
    )
except Exception:
    correct = False

feedback = (
    {"correct": True, "message": "Sıralı veride hedef geçildiğinde arama doğru biçimde duruyor."}
    if correct
    else {"correct": False, "message": "value > target olduğunda artık sonraki değerlerde hedef bulunamaz; hemen -1 döndürün."}
)
feedback

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

Solution.

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 ile tüm eşleşmeler aynı problem değildir

İlk eşleşmede bulunca durabiliriz:

if condition:
    return item

Tüm eşleşmelerde ise devam etmeliyiz:

#| edit: false
#| completion: false
def find_all_even(values):
    result = []
    for value in values:
        if value % 2 == 0:
            result.append(value)
    return result

print(find_all_even([3, 8, 11, 14, 20]))

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

11 Kayıt listesinde arama

#| edit: false
#| completion: false
students = [
    {"number": 101, "name": "Ayşe", "grade": 80},
    {"number": 102, "name": "Bora", "grade": 67},
    {"number": 103, "name": "Cem", "grade": 91},
]

def find_student(students, number):
    for student in students:
        if student["number"] == number:
            return student
    return None

print(find_student(students, 103))
print(find_student(students, 999))

Burada None, kayıt bulunamadığını temsil eder. Sonucu kullanmadan önce kontrol etmeliyiz:

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

12 Aynı aramayı çok kez yapacaksak?

Öğrenci numarasına göre tek bir arama için doğrusal dolaşma yeterli olabilir. Fakat binlerce kayıt üzerinde aynı tür 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},
}

Bu, önceki haftalardaki temel fikri tekrar gösterir:

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. Hazır min() fonksiyonu vardır; ancak algoritmayı görünür kılmak için elle uygulayalım:

#| edit: false
#| completion: false
def find_min(values):
    if not values:
        return None

    smallest = values[0]
    for value in values[1:]:
        if value < smallest:
            smallest = value

    return smallest

print(find_min([12, 5, 18, 3, 9]))
print(find_min([]))

Neden başlangıç değeri olarak 0 kullanmadık? Çünkü tüm değerler pozitif olmak zorunda değildir:

[-10, -3, -20]

Bu listede smallest = 0 ile başlamak yanlış bir sonuç üretir. Veri içinden gerçek bir eleman seçmek daha güvenlidir.

14 Kayda göre minimum/maksimum

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

#| edit: false
#| completion: false
def best_student(students):
    if not students:
        return None

    best = students[0]

    for student in students[1:]:
        if student["grade"] > best["grade"]:
            best = student

    return best

students = [
    {"name": "Ayşe", "grade": 80},
    {"name": "Bora", "grade": 67},
    {"name": "Cem", "grade": 91},
]

print(best_student(students))

15 Sınır 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.

#| edit: false
#| completion: false
def linear_search(values, target):
    for i in range(len(values)):
        if values[i] == target:
            return i
    return -1

assert linear_search([], 5) == -1
assert linear_search([5], 5) == 0
assert linear_search([5], 9) == -1
assert linear_search([2, 2, 2], 2) == 0
assert linear_search([1, 3, 5, 7], 7) == 3

print("Tüm kontroller geçti")

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.
• Sıralı doğrusal aramada hedefi geçtiğimiz anda bazı başarısız aramaları erken bitirebiliriz.
• Bu erken durma avantajına rağmen en kötü durumda doğrusal arama yine O(n)’dir.
• Bulunamama durumu -1 veya None gibi açık bir sözleşmeyle yönetilmelidir.
• Minimum/maksimum bulma da doğrusal dolaşma kalıbına dayanır.
• Çok sık yapılan belirli aramalar için veriyi sözlük gibi farklı yapıda düzenlemek 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. Bu erken durma neden en kötü durum karmaşıklığını O(n)’den değiştirmez?
4. İlk eşleşme ile tüm eşleşmeler arasında algoritmik fark nedir?
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?