Solvequill Blog · coding · 3 dk okuma · 10 görüntülenme

İkili arama neden bazen hiç bitmiyor?

Tek karakterlik bir eksik, fonksiyonu bazı girdilerde sonsuza kadar çalıştırıyor. Hatayı bulmanın yolu, aralığın küçüldüğünü kanıtlamaktır.

Yayın tarihi: 25 Ağustos 2026

Ders yükleniyor…

Bu soruyu Solvequill'in anlattığı ders.

Soru

Aşağıdaki ikili arama fonksiyonu doğru sonuçlar veriyor gibi görünüyor ama bazı girdilerde asla sonlanmıyor. Hatayı bulunuz, neden sonsuz döngüye girdiğini açıklayınız ve düzeltiniz.

Aynı satırın tekrar etmesi, sonsuz döngünün kanıtıdır.

Önce neyi fark etmeli

Bir döngünün biteceğini garanti eden şey, her adımda arama aralığının kesinlikle küçülmesidir. Bu koddaki hata bir mantık hatası değil, bir 'ilerleme' hatası: belirli bir durumda aralık hiç daralmıyor.

Adım adım çözüm

Hatalı kod. İlk bakışta makul görünüyor:

Python

1def ikili_ara(dizi, hedef):2    alt, ust = 0, len(dizi) - 13    while alt < ust:4        orta = (alt + ust) // 25        if dizi[orta] == hedef:6            return orta7        elif dizi[orta] < hedef:8            alt = orta          # HATA burada9        else:10            ust = orta - 111    return -1

Küçük bir örnekle elle izle. dizi = [1, 3] ve hedef $= 3$ olsun. Başlangıçta alt $= 0, u s t = 1$ :

or t a = ⌊ \frac{0 + 1}{2} ⌋ = 0

$d i z i [0] = 1 < 3$ olduğu için alt $= or t a = 0$ atanıyor. Ama alt zaten 0'dı. Aralık hiç küçülmedi ve bir sonraki tur birebir aynı hesabı yapacak — döngü sonsuza kadar sürer.

(a l t, u s t) = (0, 1) \to (0, 1) \to (0, 1) \dots

Düzeltme tek kelime: orta zaten kontrol edildiğine göre onu aralığın dışında bırak.

Python

1elif dizi[orta] < hedef:2 alt = orta + 1 # artık aralık her turda küçülüyor

Artık her turda ya alt büyüyor ya da ust küçülüyor, yani (ust - alt) kesin olarak azalıyor. Sıfıra ulaşınca döngü biter; sonlanma böyle kanıtlanır.

u s t - a l t her turda en az 1 azal ı r

Cevap

alt = orta + 1

Simetrik tarafta ust = orta - 1 zaten doğru yazılmıştı; hata yalnızca bir kolda olduğu için kod çoğu girdide düzgün çalışıyor ve testlerden geçebiliyor.

Bu soruda en sık yapılan hata

İzlemeyi mi tercih edersin? Yukarıdaki ders her satırı tek tek anlatıyor.

Kendi sorunu açıklamalı videoya dönüştür

Soruyu yaz veya fotoğrafını yükle; Solvequill çözümü adım adım anlatan bir video üretsin.

Solvequill'i aç