---
title: 'Doğrusal Arama'
source: 'https://academia.sh/tr/kurslar/algoritmalar/dogrusal-arama'
course: Algoritmalar
language: tr
updated: '2026-08-17T18:07:42+00:00'
license: 'CC BY-SA 4.0'
---

# Doğrusal Arama

Sırasız veride tarama, başarılı ve başarısız aramanın beklenen karşılaştırma sayısı, nöbetçi değişkeni ve doğrusal alt sınırın gerekçesi.

Çözümleme araçları hazır; bu konu onları ilk kez bir algoritma ailesine uygular. Arama ve
sıralama, aynı problemin farklı maliyetlerdeki çözümlerini yan yana koymaya elverişli
olduğu için bu iş için uygun bir zemindir.

En basit aramayla başlanır: elemanları baştan sona gezmek.

## Algoritma ve Doğruluğu

**Doğrusal arama**, diziyi baştan sona tarar ve aranan değeri bulduğu ilk konumu döndürür.

```python
def dogrusal_arama(dizi: list[int], hedef: int) -> int:
    """Hedefin ilk konumu; yoksa -1.

    Değişmez: her turun başında, 0..i-1 aralığında hedef yoktur.
    Sonlanma: kalan eleman sayısı her turda bir azalır.
    """
    for i in range(len(dizi)):
        if dizi[i] == hedef:
            return i
    return -1


olcumler = [5, 2, 9, 1, 5, 6]
print(dogrusal_arama(olcumler, 9))     # 2
print(dogrusal_arama(olcumler, 5))     # 0   — ilk eşleşme
print(dogrusal_arama(olcumler, 7))     # -1
```

Doğruluğu belgedeki iki cümle verir. Döngü değişmezi, döngü bittiğinde "0..n-1 aralığında
hedef yoktur" hâline gelir; bu da `-1` dönüşünü gerekçelendirir. Azalan büyüklük, sonlanma
güvencesidir.

İki tasarım kararı örtük olarak alınmıştır: eşit değerler varsa **ilk** konum döndürülür
ve bulunamama, geçerli bir dizin olamayacak bir değerle bildirilir.

## Üç Durumun Maliyeti

Ölçüt karşılaştırma sayısıdır.

**En iyi durum:** Hedef ilk elemandır; 1 karşılaştırma, $O(1)$.

**En kötü durum:** Hedef son elemandır veya hiç yoktur; $n$ karşılaştırma, $O(n)$.

**Ortalama durum:** Hedefin dizide bulunduğu ve her konumun eşit olasılıklı olduğu
varsayılırsa, beklenen karşılaştırma sayısı

$$
\frac{1 + 2 + \dots + n}{n} = \frac{n+1}{2}
$$

olur; bu da $O(n)$'dir. Başarısız aramada her zaman $n$ karşılaştırma yapılır.

```python
def karsilastirma_sayisi(dizi: list[int], hedef: int) -> int:
    for i in range(len(dizi)):
        if dizi[i] == hedef:
            return i + 1
    return len(dizi)


dizi = list(range(100))
toplam = sum(karsilastirma_sayisi(dizi, h) for h in dizi)
print(toplam / len(dizi))                    # 50.5   — (n+1)/2
print(karsilastirma_sayisi(dizi, -1))        # 100    — başarısız arama
```

Ortalama, en kötü durumun yaklaşık yarısıdır. Sabit çarpan farkı asimptotik sınıfı
değiştirmez: iki durum da doğrusaldır. Bu, ortalama durum çözümlemesinin ne zaman anlamlı
olduğunu gösterir — sınıfı değil, sabiti belirler.

## Nöbetçi Değişkeni

Döngü her turda iki sınama yapar: dizin sınırı aşıldı mı, eleman hedefe eşit mi. Hedef
dizinin sonuna geçici olarak eklenirse, sınır sınaması gereksizleşir; arama en geç o
elemanda durur.

```python
def nobetci_ile_arama(dizi: list[int], hedef: int) -> int:
    dizi.append(hedef)                 # nöbetçi
    i = 0
    while dizi[i] != hedef:
        i += 1
    dizi.pop()
    return i if i < len(dizi) else -1


d = [5, 2, 9, 1, 5, 6]
print(nobetci_ile_arama(d, 9), nobetci_ile_arama(d, 7), d)   # 2 -1 [5, 2, 9, 1, 5, 6]
```

Kazanç sabit çarpandadır; sınıf yine $O(n)$'dir. Yöntemin bedeli, diziyi geçici olarak
değiştirmesidir — paylaşılan veride veya çok iş parçacıklı bir ortamda kullanılamaz.

Bu, kursun tekrar eden bir dersidir: sabit iyileştirmeler gerçektir ama sınıfı değiştiren
bir fikrin yerini tutmaz.

## Neden Daha İyisi Yapılamaz

Sırasız bir dizide aramanın maliyeti düşürülemez ve bunun gerekçesi bir **karşı oyuncu**
akıl yürütmesidir.

Bir algoritmanın $n$ elemanın hepsine bakmadığını varsayalım. Bakmadığı en az bir konum
vardır. Karşı oyuncu, algoritma "bulunamadı" dediğinde o konuma hedefi yerleştirir;
algoritmanın gözlemleri değişmediği için yanıtı da değişmez, ama yanıt artık yanlıştır.

Öyleyse doğru çalışan her algoritma, en kötü durumda tüm elemanlara bakmak zorundadır:
sırasız veride arama $\Omega(n)$'dir. Doğrusal arama bu sınıra ulaştığı için, sıra
varsayımı olmadan **eniyi**dir.

Sınırdan kaçmanın tek yolu varsayımı değiştirmektir: veriyi sıralı tutmak veya bir dizin
yapısı kurmak. Sonraki ders birinci yolu, Veri Yapıları kursundaki karma tablosu ikinci
yolu izler.

## Erişim Dağılımı ve Sıralamanın Etkisi

Ortalama durum hesabı, her elemanın eşit olasılıkla arandığını varsayıyordu. Gerçek
erişimler çoğu zaman eşit dağılmaz: birkaç kayıt sık, geri kalanı seyrek aranır.

Beklenen karşılaştırma sayısı, $i$ numaralı elemanın aranma olasılığı $p_i$ iken

$$
\sum_{i=1}^{n} i \cdot p_i
$$

olur. İfade, elemanlar **azalan olasılık sırasına** dizildiğinde en küçük değerini alır.
Yani dizinin sırası maliyeti belirler ve en iyi statik düzen, sıklığa göre sıralamadır.

```python
def beklenen_maliyet(olasiliklar: list[float]) -> float:
    return sum((i + 1) * p for i, p in enumerate(olasiliklar))


print(round(beklenen_maliyet([0.1, 0.2, 0.7]), 2))      # 2.6   — kötü düzen
print(round(beklenen_maliyet([0.7, 0.2, 0.1]), 2))      # 1.4   — sıklığa göre
```

Sıklıklar önceden bilinmiyorsa, listeyi çalışma anında düzenleyen sezgiler kullanılır:
bulunan eleman başa taşınır ya da bir sıra öne alınır. Bunlar en kötü durumu değiştirmez —
sınıf yine $O(n)$'dir — ancak eğik dağılımlarda ortalamayı belirgin biçimde düşürür.

## Tek Geçişte Birden Çok Bilgi

Doğrusal tarama yalnızca eşleşme aramaz; aynı geçişte birkaç büyüklük birden toplanabilir.
En küçük ile en büyüğü ayrı ayrı aramak $2n$ karşılaştırma ister; elemanlar ikişer ikişer
işlenirse maliyet düşer.

```python
def en_kucuk_ve_en_buyuk(dizi: list[int]) -> tuple[int, int, int]:
    """(en küçük, en büyük, karşılaştırma sayısı) döndürür."""
    n = len(dizi)
    if n % 2 == 0:
        kucuk, buyuk = min(dizi[0], dizi[1]), max(dizi[0], dizi[1])
        i, sayac = 2, 1
    else:
        kucuk = buyuk = dizi[0]
        i, sayac = 1, 0

    while i < n - 1:
        a, b = dizi[i], dizi[i + 1]
        if a > b:
            a, b = b, a
        sayac += 3                      # çift içi + iki uçla karşılaştırma
        kucuk = min(kucuk, a)
        buyuk = max(buyuk, b)
        i += 2
    return kucuk, buyuk, sayac


print(en_kucuk_ve_en_buyuk([5, 2, 9, 1, 5, 6]))          # (1, 9, 7)
print(en_kucuk_ve_en_buyuk(list(range(100))))            # (0, 99, 148)
```

Yüz eleman için 148 karşılaştırma yapılır; ayrı ayrı arama 198 isterdi. Genel formül
$3n/2 - 2$'dir ve bu, iki uç için bilinen alt sınırdır.

Sınıf yine $O(n)$'dir. Kazanç, veri diskten veya ağdan geliyorsa ve her geçiş pahalıysa
önem kazanır: tek geçişte toplanabilecek her bilgi, ikinci bir geçişten ucuzdur.

## Özet

- Doğrusal arama sırasız veride çalışır; doğruluğu döngü değişmezi ve azalan büyüklükle
  gerekçelendirilir.
- En iyi durum sabit, en kötü durum doğrusaldır; başarılı aramanın beklenen maliyeti
  $(n+1)/2$ karşılaştırmadır.
- Nöbetçi değişkeni sınır sınamasını kaldırır; kazanç sabit çarpandadır, sınıf değişmez.
- Karşı oyuncu akıl yürütmesi, sırasız veride aramanın $\Omega(n)$ olduğunu gösterir;
  doğrusal arama bu sınıra ulaşır.
- Erişim olasılıkları eşit değilse, elemanları azalan sıklıkla dizmek beklenen maliyeti
  düşürür.
- Tek geçişte birden çok büyüklük toplamak, geçiş sayısını ve toplam karşılaştırmayı
  düşürür.

## Sonraki Adım

Doğrusal alt sınırdan kaçmanın yolu, veri üzerinde bir varsayım kurmaktır. Veri sıralıysa
her karşılaştırma yalnızca bir elemanı değil, elemanların yarısını eler. Sonraki ders bu
fikri — ikili aramayı — ve doğru yazılması şaşırtıcı derecede zor olan sınır koşullarını
ele alacak.