---
title: 'İkili Arama'
source: 'https://academia.sh/tr/kurslar/algoritmalar/ikili-arama'
course: Algoritmalar
language: tr
updated: '2026-08-17T18:07:40+00:00'
license: 'CC BY-SA 4.0'
---

# İkili Arama

Sıralı veride yarıya bölme, döngü değişmeziyle sınır koşulları, ilk konumu bulan değişkeler ve tekdüze yüklem üzerinde arama.

Doğrusal arama sırasız veri için eniyiydi. Varsayım değişirse sınır da değişir: dizi
sıralıysa, bir karşılaştırma tek bir elemanı değil, kalan elemanların **yarısını** eler.

Bu ders o fikri işler. Fikir basittir; doğru yazmak değildir — ikili arama, yayımlanmış
gerçekleştirimlerinde onlarca yıl hata barındırmış olmasıyla tanınır.

## Aralık Değişmezi

Algoritma, hedefin bulunabileceği bir aralık tutar ve her turda aralığı yarıya indirir.
Sınır hatalarından kaçınmanın yolu, aralığın anlamını en baştan yazmaktır.

Bu derste **kapalı aralık** kullanılır: `[sol, sag]` sınırlarının ikisi de aralığa
dahildir.

```python
def ikili_arama(dizi: list[int], hedef: int) -> int:
    """Sıralı dizide hedefin bir konumu; yoksa -1.

    Değişmez: hedef dizide varsa, [sol, sag] aralığındadır.
    Sonlanma: sag - sol her turda en az bir azalır.
    """
    sol, sag = 0, len(dizi) - 1
    while sol <= sag:
        orta = sol + (sag - sol) // 2
        if dizi[orta] == hedef:
            return orta
        if dizi[orta] < hedef:
            sol = orta + 1
        else:
            sag = orta - 1
    return -1


sirali = [1, 3, 4, 7, 9, 11, 15, 20]
print(ikili_arama(sirali, 9))      # 4
print(ikili_arama(sirali, 1))      # 0
print(ikili_arama(sirali, 20))     # 7
print(ikili_arama(sirali, 10))     # -1
```

Üç ayrıntı, gerçekleştirimin doğruluğunu taşır:

**Döngü koşulu `sol <= sag`.** Aralık kapalı olduğu için tek elemanlı aralık da geçerlidir;
`<` yazılırsa son eleman hiç sınanmaz.

**Sınırların `orta ± 1` ile güncellenmesi.** Sınanan eleman aralığın dışında bırakılır.
`sag = orta` yazılırsa aralık küçülmeyebilir ve döngü sonsuza girer — sonlanma güvencesi
tam olarak bu adımdan gelir.

**Orta noktanın `sol + (sag - sol) // 2` ile hesaplanması.** `(sol + sag) // 2` yazımı,
sabit genişlikli tam sayı kullanan dillerde büyük dizilerde taşabilir. Bilgisayarlar Nasıl
Çalışır kursundaki taşma davranışı burada somut bir hataya dönüşür.

## Maliyet

Her tur aralığı yarılar ve sabit iş yapar:

$$
T(n) = T(n/2) + O(1) \implies T(n) = O(\log n)
$$

En kötü durumda karşılaştırma sayısı $\lfloor \log_2 n \rfloor + 1$'dir.

```python
from collections.abc import Sequence


def sayimli_ikili_arama(dizi: Sequence[int], hedef: int) -> tuple[int, int]:
    sol, sag, sayac = 0, len(dizi) - 1, 0
    while sol <= sag:
        orta = sol + (sag - sol) // 2
        sayac += 1
        if dizi[orta] == hedef:
            return orta, sayac
        if dizi[orta] < hedef:
            sol = orta + 1
        else:
            sag = orta - 1
    return -1, sayac


for n in (1_000, 1_000_000, 1_000_000_000):
    # range dizinlenebilir olduğu için milyarlık dizi bellek ayrılmadan sınanır
    cift_sayilar = range(0, 2 * n, 2)
    print(n, sayimli_ikili_arama(cift_sayilar, n + 1)[1])   # tek sayı: dizide yok

# 1000 10
# 1000000 20
# 1000000000 30
```

Milyar elemanlı bir dizide otuz karşılaştırma yeterlidir. Doğrusal arama aynı işi bir
milyar karşılaştırmayla yapar — Karmaşıklık Sınıflarını Okumak dersindeki ölçek büyütme
tablosunun somut karşılığı budur.

Alan maliyeti $O(1)$'dir. Aynı algoritma özyinelemeli de yazılabilir, ancak o durumda
$O(\log n)$ yığıt alanı kullanır.

## Alt Sınır: Neden Daha Hızlısı Yok

Karşılaştırmaya dayalı arama, her adımda üç sonuçtan birini üretir: küçük, eşit, büyük.
Algoritmanın davranışı bir karar ağacı olarak çizilirse, ağacın her yaprağı olası bir
yanıttır ve $n$ elemanlı dizide en az $n$ farklı yanıt vardır.

Yüksekliği $h$ olan ikili bir ağacın en çok $2^h$ yaprağı olabilir. $2^h \geq n$
koşulundan $h \geq \log_2 n$ çıkar: karşılaştırmalı arama $\Omega(\log n)$'dir.

Aynı karar ağacı fikri, sıralamanın alt sınırında yeniden kullanılacak.

## İlk ve Son Konum

Dizide yinelenen değerler varsa, yukarıdaki gerçekleştirim **herhangi** bir eşleşmeyi
döndürür. Sıralamayla ilgili birçok işlem ise ilk eşleşmeyi ister.

**Alt sınır (lower bound)**, hedeften küçük olmayan ilk elemanın konumudur. Eşleşme yoksa,
hedefin sıralamayı bozmadan eklenebileceği yeri verir.

```python
def alt_sinir(dizi: list[int], hedef: int) -> int:
    """dizi[i] >= hedef koşulunu sağlayan en küçük i (yoksa len(dizi)).

    Değişmez: yanıt [sol, sag] aralığındadır; aralık yarı açık tutulur.
    """
    sol, sag = 0, len(dizi)
    while sol < sag:
        orta = sol + (sag - sol) // 2
        if dizi[orta] < hedef:
            sol = orta + 1
        else:
            sag = orta
    return sol


tekrarli = [1, 3, 3, 3, 7, 9, 9]
print(alt_sinir(tekrarli, 3))      # 1   — ilk 3
print(alt_sinir(tekrarli, 9))      # 5   — ilk 9
print(alt_sinir(tekrarli, 4))      # 4   — eklenecek yer
print(alt_sinir(tekrarli, 10))     # 7   — dizinin sonu
```

Bu değişke **yarı açık** aralık kullanır: `sag` aralığa dahil değildir. Bu yüzden döngü
koşulu `sol < sag` ve güncelleme `sag = orta`'dır. İki değişkeyi karıştırmak, ikili
aramadaki hataların en yaygın kaynağıdır — aralığın hangi biçimde tutulduğu bir kez
seçilir ve tüm satırlar ona göre yazılır.

Üst sınır, hedeften **büyük** ilk elemanı bulur; iki sonucun farkı, hedefin dizide kaç kez
geçtiğini verir.

## Sıralı Dizinin Ötesinde

İkili aramanın gerçek koşulu "dizi sıralı" değil, daha geneldir: **tekdüze bir yüklem**
bulunmasıdır. Bir koşul, belirli bir noktaya kadar yanlış ve o noktadan sonra hep doğruysa,
o nokta ikili aramayla bulunabilir.

```python
def tam_karekok(n: int) -> int:
    """k*k <= n koşulunu sağlayan en büyük k."""
    sol, sag, yanit = 0, n, 0
    while sol <= sag:
        orta = sol + (sag - sol) // 2
        if orta * orta <= n:
            yanit = orta
            sol = orta + 1
        else:
            sag = orta - 1
    return yanit


print(tam_karekok(0), tam_karekok(15), tam_karekok(16), tam_karekok(10**18))
# 0 3 4 1000000000
```

Ortada bir dizi yoktur; aranan şey, `orta * orta <= n` yükleminin doğru kaldığı son
değerdir. Yüklem tekdüze olduğu için yarıya bölme geçerlidir.

Bu genelleme yaygın bir tasarım aracıdır: "en küçük yeterli kapasite", "en büyük geçerli
eşik" biçimindeki problemler, doğrudan denenecek değer aralığı üzerinde ikili aramayla
çözülür.

## Ne Zaman Kullanılmaz

İkili arama üç varsayıma dayanır ve biri bozulduğunda tercih edilmez.

**Sıralılık bedavaya gelmiyorsa.** Tek bir arama için diziyi sıralamak $O(n \log n)$'dir;
doğrusal arama $O(n)$. Sıralama ancak çok sorgulu kullanımda kendini öder.

**Rastgele erişim yoksa.** Bağlı listede orta elemana gitmek doğrusaldır ve logaritmik
kazanç yok olur. Veri Yapıları kursundaki arama ağaçları, tam olarak bu boşluğu doldurur.

**Veri sürekli değişiyorsa.** Her eklemede sıralı diziyi güncellemek $O(n)$'dir; bu
durumda dengeli ağaç veya karma tablosu daha uygundur.

## Özet

- İkili arama sıralı veride aralığı yarılar; doğruluğu, aralığın anlamını sabit tutan bir
  değişmezle gerekçelendirilir.
- Kapalı ve yarı açık aralık değişkeleri farklı döngü koşulu ve güncelleme ister; ikisi
  karıştırılmamalıdır.
- Maliyet $T(n) = T(n/2) + O(1)$ bağıntısından $O(\log n)$ çıkar; alan $O(1)$'dir.
- Karar ağacı akıl yürütmesi, karşılaştırmalı aramanın $\Omega(\log n)$ olduğunu gösterir.
- Alt sınır değişkesi ilk eşleşmeyi veya ekleme konumunu verir.
- Yöntem, tekdüze bir yüklemin doğru olduğu ilk değeri arayan her probleme uygulanır.

## Sonraki Adım

İkili aramanın koşulu sıralılıktı; öyleyse sıralamanın kendisi incelenmelidir. Sonraki
ders üç temel sıralama algoritmasını — kabarcık, seçmeli ve eklemeli — karesel maliyetleri,
kararlılıkları ve birbirlerinden ayrıldıkları noktalarla ele alacak.