Arama algoritmaları

Murad 1 ile 100 arasında bir sayı tutuyor, Aysel de onu bulmalı. Her tahminden sonra Murad yalnızca “daha büyük”, “daha küçük” ya da “doğru” diyor. Aysel 1, 2, 3… diye sırayla sorarsa 100 tahmin gerekebilir. Ama 50'den başlayıp her seferinde aralığı ikiye bölerse sayıyı en fazla 7 tahminde bulur. Bu iki yaklaşım iki ünlü algoritmadır: doğrusal arama ve ikili arama.

Doğrusal arama

Doğrusal (sıralı) aramada listenin elemanları ilkinden başlayarak tek tek aranan değerle karşılaştırılır. Eşleşen eleman bulununca arama durur; listenin sonuna gelip bulamazsak bu eleman listede yoktur.

Doğrusal aramanın avantajı basitliğidir: her listede, sıralı olmasa bile çalışır. Dezavantajı ise yavaşlığıdır: n elemanlı bir listede en kötü durumda n karşılaştırma gerekir.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

numbers = [7, 3, 23, 9, 15]
print(linear_search(numbers, 23))
print(linear_search(numbers, 4))

2
-1

İkili arama

İkili arama yalnızca sıralı (örneğin küçükten büyüğe dizilmiş) bir listede çalışır ama çok hızlıdır. Her adımda aranan değer aralığın ortasındaki elemanla karşılaştırılır ve listenin yarısı bir anda elenir.

1. 1
   Ortayı bul

   Arama aralığının ortasındaki elemanı al.

2. 2
   Karşılaştır

   Ortadaki eleman aranan değere eşitse eleman bulunmuştur, arama biter.

3. 3
   Yarısını ele

   Aranan değer ortadaki elemandan küçükse sol yarıda, büyükse sağ yarıda aramaya devam et.

4. 4
   Tekrarla

   Eleman bulunana ya da aralık boşalana kadar 1–3. adımları tekrarla. Aralık boşsa eleman listede yoktur.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    steps = 0
    while low <= high:
        mid = (low + high) // 2
        steps += 1
        if items[mid] == target:
            return mid, steps
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, steps

numbers = [3, 8, 12, 17, 23, 31, 37, 42, 50]
print(binary_search(numbers, 37))
print(binary_search(numbers, 5))

(6, 2)
(-1, 3)

Hangisi daha hızlı?

İkili aramada her karşılaştırma listeyi yarıya indirir; bu yüzden liste iki katına çıkınca yalnızca bir karşılaştırma eklenir. Büyük listelerde fark şaşırtıcıdır: