Doğrusal arama nedir?

Question

Accepted Answer

**Doğrusal arama** hedefi bulana veya sona ulaşana kadar bir koleksiyonu öğe öğe tarar. **Herhangi** bir listede çalışır — sıralanmış olsun ya da olmasın — ancak **O(n)** zamanında çalışır.

## Fikir

Sıra hakkında hiçbir varsayım yok: sadece her öğeyi teker teker kontrol et.

## Örnek

```python
def linear_search(arr, target):
    for i, value in enumerate(arr):   # walk left to right
        if value == target:
            return i                  # return the index when found
    return -1                         # not found after full scan

linear_search([4, 2, 7, 1], 7)        # -> 2
```

## Karmaşıklık

- **Zaman:** O(n) en kötü durum (hedef son veya yok), O(1) en iyi durum.
- **Alan:** O(1).

## Ne zaman kullanılır

- Veriler **sıralanmamış** ve sıralayamazsınız.
- Liste küçük, bu yüzden O(n) ihmal edilebilir.
- Tek seferlik arama yapmanız gerekir, bu durumda indeks oluşturmak veya önceden sıralamak gereksiz.

Sık sık arama yaparsanız, ikili arama ile sıralanmış bir diziyi veya O(1) ortalama aramalar için hash set'i tercih edin.

## Neden önemli

Doğrusal arama, diğer tüm aramaların karşılaştırıldığı temel noktadır.

Sana *doğru* algoritmanın veriye bağlı olduğunu hatırlatır: sıralanmamış ve küçük veriler basit taramayı tercih ettirir; büyük ve tekrar tekrar sorgulanan veriler daha akıllı yapıları tercih ettirir.

O(n)'in ne zaman yeterli olduğunu bilmek erken optimizasyonu engeller.