Doğrusal Arama

#Nasıl çalışır?

Doğrusal arama (linear search), aranan değeri bulmak için dizinin başından başlar ve elemanları tek tek kontrol eder. Bulursa sırasını döndürür, sona kadar bulamazsa "yok" der.

En basit arama yöntemidir ve verinin sıralı olmasını gerektirmez. Dizi, bağlı liste ya da dosya satırları gibi sırayla gezilebilen her veride çalışır.

Bedeli ise süredir: en kötü durumda (değer sonda ya da hiç yoksa) bütün elemanlara bakmak gerekir.

#Canlı animasyon

for i = 0 to n - 1
  if a[i] == target: return i
return -1

#Adım adım

1. 01İlk elemandan başla.
2. 02Elemanı aranan değerle karşılaştır.
3. 03Eşitse sırasını döndür ve dur.
4. 04Eşit değilse bir sonraki elemana geç.
5. 05Dizinin sonuna gelirsen değer yoktur; -1 döndür.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def linear_search(a: list[int], target: int) -> int:
    """Returns the index of the first element equal to target, or -1."""
    for i, value in enumerate(a):
        if value == target:
            return i
    return -1


numbers = [4, 8, 1, 9, 3]
print(linear_search(numbers, 9))
print(linear_search(numbers, 7))

#Karmaşıklık

Değer ilk sıradaysa tek karşılaştırma yeter. Ortalamada elemanların yarısına, değer yoksa hepsine bakılır. Veri bir kez sıralanıp çok kez aranacaksa ikili arama çok daha hızlıdır.

#Ne zaman kullanılır?

Küçük ya da sıralı olmayan verilerde, tek seferlik aramalarda ve bağlı liste gibi indeksle erişilemeyen yapılarda doğru seçimdir. Programlama dillerindeki indexOf, includes ve find gibi fonksiyonlar doğrusal arama yapar.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• İkili Arama
• Düz Desen Arama