--- title: 'İkili Arama ile Hata Avı' source: 'https://academia.sh/tr/kurslar/ileri-git/ikili-arama-ile-hata-avi' course: 'İleri Git' language: tr updated: '2026-08-17T18:10:42+00:00' license: 'CC BY-SA 4.0' --- # İkili Arama ile Hata Avı Tarihçeye soru sormanın bedeli adım sayısıdır: aynı kusuru bulmak için doğrusal tarama 37, 150, 750 ve 3000 adım harcarken ikili arama 6, 7, 9 ve 11 adımda bitirir, ve aramayı ucuzlatan toplama yanıtın çözünürlüğünü kabalaştırır. Önceki ders yeniden yazmanın ardından geriye ne kaldığını saydı: kaybolan işlemeler referans günlüğünde bir süre daha erişilebilir kalıyor, çöp toplama çalışınca o pencere kapanıyordu. Buraya kadar tarihçe **değiştirilen** bir nesneydi ve her değişikliğin bedeli dokunulan nesneyle ölçüldü. Bu ders yönü çeviriyor. Tarihçeye dokunmuyoruz, ona **soru soruyoruz**: bu kusur hangi işlemede girdi? Bedelin birimi de değişiyor. Burada sayılan şey dokunulan nesne değil, **adım** — yani kâhine kaç kez başvurulduğu. Sorunun yanıtı tarihçenin içinde duruyor; mesele onu kaç denemede çıkarabildiğimiz. ## Aramanın Dayandığı Tek Varsayım Tarihçe boyunca her işleme için tek bir soru sorulabilir: kusur burada var mı? Yanıt bir noktaya kadar "yok", o noktadan sonra hep "var" ise, tarihçe bu soru açısından **tekdüzedir**. Aranan şey, yanıtın döndüğü ilk işlemedir. Bu tekdüzelik bir armağan değil, bir varsayımdır ve bozulabilir. Kusur girmiş, sonra bir başka işlemede yanlışlıkla örtülmüş, sonra yeniden açığa çıkmışsa yanıt iki kez döner ve arama yanlış işlemeyi gösterir. Aramayı kurmadan önce sorulacak soru budur: bu koşul tarihçe boyunca bir kez mi değişiyor? Tekdüze bir yüklem üzerinde aralığı yarılayan algoritmanın kendisi Algoritmalar kursunun Arama ve Sıralama konusunda kuruldu; orada ölçülen şey **algoritmanın karmaşıklığıydı**. Burada ölçülen şey başka: aynı yöntem bir işleme dizisine uygulandığında **tarihçe üzerinde kaç adım** harcandığı. Aracın alt komutu bu yöntemi tarihçeye bağlar ve her adımda çalışma alanını o işlemeye taşır. ## Aracın Yürüttüğü Döngü Arama üç bildirimle kurulur: aramanın başlatılması, kusurun görüldüğü bir işleme ve kusurun görülmediği bir işleme. Bundan sonrasını araç yürütür; her adımda aralığın ortasındaki işlemeye geçer ve yanıtı bekler. ```text # öğretilen komutlar ve örnek döküm — çalıştırılmamıştır git bisect start git bisect bad HEAD git bisect good v-onceki-surum # araç aralığın ortasına geçer ve kalan aday sayısını bildirir: Bisecting: revisions left to test after this [a1b2c3d] olcum: esik degerini ayardan oku # her adımda yanıt verilir git bisect good # ya da: git bisect bad # arama bittiğinde aracın çalışma alanı geri alınır git bisect reset ``` İki ucun seçimi aramanın tek serbest parametresidir ve iki yönde de yanlış seçilebilir. Kusursuz uç gereğinden geriye konursa aday kümesi büyür ve her fazladan iki katı bir adım daha ödetir. Gereğinden ileriye konursa daha kötüsü olur: kusur o ucun gerisinde kalır, arama tekdüzelik varsayımını sağlamayan bir küme üzerinde yürür ve yine bir işleme gösterir. Yanlış uç seçiminin belirtisi yoktur; aramanın sonunda dönen işleme her iki durumda da aynı biçimde bildirilir. Yanıtı elle vermek zorunlu değildir. Kusuru sınayan bir betik varsa arama tümüyle araca bırakılabilir; betiğin çıkış kodu kâhin yerine geçer, sıfır "kusur yok", sıfırdan farklı "kusur var" demektir. Bu ayrım pratikte belirleyicidir: kâhin otomatikleştirilemiyorsa adım sayısı doğrudan insan emeğine dönüşür. Aramanın bir de eksik yanıtı vardır. Aralığın ortasındaki işleme kurulmuyorsa ya da o noktada sınama anlamlı değilse, o işleme yanıt veremez ve arama onu **atlamak** zorunda kalır. Atlanan işleme aralığı yarılamaz; yalnızca komşusuna kayar. Kurulmayan bir pencere tarihçenin ortasındaysa, arama o pencerenin genişliği kadar adımı yarılama olmadan harcar. Ölçümün varsayımları: - **TA1** — Tarihçe ortak kurgudan üretilir: dört ölçekte doğrusal bir işleme dizisi, her işleme beş dosyadan birine dokunuyor. - **TA2** — Kâhin kurguyu biz ürettiğimiz için bilinir ve kusurun tarihçenin dörtte üçünde girdiğini söyler. Kâhin her ölçekte aynı kuraldır ve ölçüm boyunca değiştirilmez. - **TA3** — Tekdüzelik varsayılır: kusur girdiği işlemeden sonra hiç kapanmaz. Ölçüm tekdüzeliğin bozulduğu durumu saymaz. - **TA4** — Bir adım, kâhine yapılan bir başvurudur. Kurulum, sınama ve çalışma alanının taşınması bir adımın içinde sayılır; adımlar birbirinden ayırt edilmez. - **TA5** — Doğrusal tarama tarihçeyi baştan sona yürür ve kusuru gördüğü ilk işlemede durur. Bu, aramanın en iyi durumda değil, **kurgunun verdiği durumda** ölçülmesidir. - **TA6** — İkinci bölümde tek değişen şey işlemelerin toplanma oranıdır: aynı değişiklikler, her biri daha az sayıda işlemede kayıtlı. Kurgu ve kâhin aynı kalır. - **TA7** — Kurgu doğrusaldır: aday kümesi iki sayı arasındaki aralıktır. Çatallanmış tarihçede aday kümesinin nasıl kurulduğu ölçümün dışında, ölçümün ardındaki bölümde tartışılır. ## Ölçüm ```python """Tarihcede kusurlu islemeyi bulmanin bedeli: adim sayisi. Bolum 1 - iki tarama bicimi dort olcekte. Bolum 2 - aramanin ucuzlamasi ile yanitin kabalasmasi. """ TOHUM = 20260814 DOSYALAR = ("olcum.py", "rapor.py", "kimlik.py", "ayar.py", "belge.md") def uretec(tohum): d = tohum % 2147483646 + 1 def r(n): nonlocal d d = (d * 48271) % 2147483647 return d % n return r def tarihce(n, tohum=TOHUM): """n islemelik dogrusal tarihce; her isleme bir dosyaya dokunuyor.""" r, liste = uretec(tohum), [] for i in range(n): dosya = DOSYALAR[r(5)] ikili = r(11) == 0 liste.append({"no": i + 1, "dosya": dosya, "ikili": ikili, "nesne": 2 + (40 if ikili else 0)}) return liste def kusurlu_isleme(t): """Kahin: kusuru getiren isleme, kurguyu biz yazdigimiz icin bilinir.""" return len(t) * 3 // 4 def dogrusal_arama(t): hedef, adim = kusurlu_isleme(t), 0 for x in t: adim += 1 if x["no"] >= hedef: return adim return adim def ikili_arama(t): hedef, alt, ust, adim = kusurlu_isleme(t), 1, len(t), 0 while alt < ust: orta = (alt + ust) // 2 adim += 1 if orta >= hedef: ust = orta else: alt = orta + 1 return adim def aday_izi(t): """Her adimdan sonra geriye kalan aday isleme sayisi.""" hedef, alt, ust, iz = kusurlu_isleme(t), 1, len(t), [] while alt < ust: orta = (alt + ust) // 2 if orta >= hedef: ust = orta else: alt = orta + 1 iz.append(ust - alt + 1) return iz def toplanmis(t, k): """Ayni degisiklikler, k tanesi tek islemede kayitli.""" return [{"no": i + 1, "nesne": sum(x["nesne"] for x in t[i * k:(i + 1) * k])} for i in range(len(t) // k)] OLCEKLER = (50, 200, 1000, 4000) print(f"{'işleme':>7s} {'kusurlu':>8s} {'doğrusal adım':>14s} {'ikili adım':>11s}") for n in OLCEKLER: t = tarihce(n) print(f"{n:7d} {kusurlu_isleme(t):8d} {dogrusal_arama(t):14d} " f"{ikili_arama(t):11d}") buyuk = tarihce(4000) print() print("4000 işlemede adım adım kalan aday:", aday_izi(buyuk)) print() print(f"{'işleme':>7s} {'toplama':>8s} {'ikili adım':>11s} {'yanıtın kapsamı':>16s}") for k in (1, 2, 5, 10, 40): g = toplanmis(buyuk, k) print(f"{len(g):7d} {k:8d} {ikili_arama(g):11d} {k:16d}") ``` ``` işleme kusurlu doğrusal adım ikili adım 50 37 37 6 200 150 150 7 1000 750 750 9 4000 3000 3000 11 4000 işlemede adım adım kalan aday: [2000, 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1] işleme toplama ikili adım yanıtın kapsamı 4000 1 11 1 2000 2 10 2 800 5 9 5 400 10 8 10 100 40 6 40 ``` ## İki Bedelin Ayrıştığı Yer Üst tablo aynı tarihçeyi iki biçimde tarıyor. Tarihçe **50**'den **4000**'e, yani seksen kat büyürken doğrusal tarama **37** adımdan **3000** adıma çıkıyor; ikili arama **6** adımdan **11**'e. **Seksen kat büyüyen bir tarihçede ikili arama iki kat bile artmıyor.** Doğrusal taramanın sütunu ikinci sütunla birebir aynı ve bu bir tesadüf değil: doğrusal tarama kusuru gördüğü ilk işlemede durduğu için harcadığı adım, kusurun **tarihçedeki yeridir**. Yani doğrusal taramanın bedeli tarihçenin uzunluğuna değil, kusurun nereye düştüğüne bağlıdır; kusur başlarda olsaydı ucuz, sonlarda olsaydı pahalı olurdu. Ölçüm bunu bir avantaj olarak da okumuyor, çünkü kusurun nerede olduğu aramadan **önce** bilinmiyor. Bilinseydi arama zaten gerekmezdi; ölçüm de bu yüzden kusuru sabit bir yere koyar ve iki biçimi aynı koşulda karşılaştırır. İkili aramanın sütununda böyle bir bağımlılık yok. Ortadaki iz satırı nedenini gösteriyor: aday sayısı **2000**'den başlayıp her adımda yarılanarak **1**'e iniyor. Her yanıt aralığın yarısını eliyor, ve elenen yarı bir daha hiç sınanmıyor. Dört bin işlemelik tarihçede on bir yanıt, aday kümesini **1/4000** çözünürlüğüne indirmeye yetiyor. Dört ölçekte ulaşılan çözünürlük sırasıyla **1/50**, **1/200**, **1/1000** ve **1/4000**'dir; ölçüm bundan küçük bir ayrımı gösteremez, çünkü tarihçenin kendi çözünürlüğü bir işlemedir. Bu ayrım kursun ölçü ekseninin arama tarafındaki karşılığıdır: bedel tarihçenin uzunluğundan değil, **bir adımın hangi kümeye dokunduğundan** çıkıyor. Doğrusal tarama bir adımda bir işlemeye dokunuyor, ikili arama bir adımda kalan adayların yarısına. ## Çatallanmış Tarihçede Aday Kümesi Ölçümün kurgusu doğrusaldır: işlemeler bir dizi hâlindedir ve aralık iki sayı arasındadır. Gerçek bir tarihçe çoğu zaman doğrusal değildir; Dallanma ve İşbirliği kursunda kurulan birleştirme işlemesi tarihçeyi bir çizgi olmaktan çıkarır. Arama bu durumda da çalışır ama aralığın anlamı değişir. Aday kümesi artık iki sayı arasındaki işlemeler değil, **kusurlu bildirilen işlemeden erişilebilen ve kusursuz bildirilen işlemeden erişilemeyen** işlemelerdir. Araç her adımda bu kümeyi en dengeli bölen işlemeye geçer. Yarılama fikri korunur; değişen tek şey neyin yarıldığıdır. Bunun iki pratik sonucu var. Birincisi, bir yan dalda girmiş kusur o dal birleştirilene kadar ana çizgide görünmez, ama arama kusuru birleştirme işlemesinde değil yan daldaki gerçek işlemesinde bulur — çünkü o işleme de aday kümesinin içindedir. İkincisi, adım sayısını belirleyen şey iki uç arasındaki mesafe değil, **erişilebilir kümenin büyüklüğüdür**. İki uç birbirine yakın görünürken araya birleşmiş dallar geniş bir küme getiriyorsa adım sayısı o kümeye göre çıkar. ## Bir Adımın Gerçek Bedeli Adım sayısı tek başına bir emek ölçüsü değil. Her adım çalışma alanının o işlemeye taşınmasını, gerekiyorsa yeniden kurulmasını ve sınanmasını içerir. Kurulumu uzun süren bir bileşende on bir adım, kurulumu anlık olan bir bileşendeki üç bin adımdan pahalıya gelebilir. Bu yüzden aramanın pratikteki ölçüsü şudur: **adım sayısı × bir adımın süresi.** İkili arama ilk çarpanı düşürür; ikinci çarpanı düşüren şey ise aramanın kendisi değil, kusuru sınayan betiğin hızıdır. Sınama betiği kurulmuş bir ortamda saniyeler içinde yanıt veriyorsa arama tümüyle araca bırakılabilir ve on bir adım tek bir komutun içinde geçer. Sınama elle yapılıyorsa on bir adım on bir kez insan dikkati demektir. Atlanan işlemeler bu çarpımı bozan tek durumdur. Kurulmayan bir işleme yanıt üretmez; arama komşusuna kayar ve o kaymanın maliyeti yarılama olmadan ödenir. Kurulamayan pencereler geniş bir tarihçede aramayı doğrusala yaklaştırabilir. Bunun çaresi arama tarafında değil: tarihçenin her noktasında kurulabilir kalması, arama aracının değil tümleştirme disiplininin sonucudur. ## Aramanın Kaydı ve Yanıtın Doğrulanması Arama bir dizi karardan oluşur ve kararlar yanlış verilebilir. Bir adımda kusur gözden kaçırılıp "kusursuz" denmişse arama o yanıtın açtığı yönde ilerler ve sonunda yanlış bir işleme gösterir. Araç bunu fark edemez, çünkü elindeki tek bilgi verilen yanıtlardır. Buna karşı iki alışkanlık vardır. Birincisi aramanın kaydının tutulmasıdır: verilen yanıtların dizisi bir günlüğe yazılır ve gerektiğinde yeniden oynatılabilir. Yanlış verildiğinden şüphelenilen adım günlükten çıkarılıp arama o noktadan yeniden yürütülebilir; tümüyle başa dönmek gerekmez. ```text # öğretilen komutlar ve örnek döküm — çalıştırılmamıştır git bisect log > arama-kaydi.txt git bisect reset git bisect replay arama-kaydi.txt git bisect skip # sınanamayan işlemede git bisect run ./sinama.sh # kâhin betiğin çıkış kodudur ``` İkincisi, bulunan işlemenin bir yanıt değil bir **sav** olmasıdır. Arama bittiğinde elde tek bir işleme vardır ve o işlemenin gerçekten kusuru getirdiği ayrıca sınanmalıdır: değişiklik geri alındığında kusur kayboluyor mu? Bu doğrulama on bir adımın üstüne on ikinciyi ekler. Ölçümde saymadığımız bu adım pratikte atlanmaz, çünkü aramanın bütün güvencesi kâhinin verdiği yanıtların doğruluğuna dayanır. Kâhinin kesinliği de aynı yere bağlanır. "Yavaş çalışıyor" gibi bir ölçüt eşiği belirsiz bırakır ve aynı işleme iki denemede iki farklı yanıt alabilir. Kâhin ikili bir karara indirgenemiyorsa tekdüzelik varsayımı sınanamaz hâle gelir ve arama dayandığı zemini kaybeder. Aramanın kurulmasındaki asıl iş bu yüzden komutlarda değil, kusuru bir çıkış koduna indiren betiği yazmaktadır. ## Yanıtın Çözünürlüğü Alt tablo aynı değişiklikleri farklı büyüklükte işlemelere toplayarak aynı aramayı yeniden yapıyor. Dört bin değişiklik kırklı gruplara toplandığında tarihçe **100** işlemeye iniyor ve arama **11** yerine **6** adımda bitiyor. Beş adım kazanç. Bedeli sağdaki sütunda: yanıtın kapsamı **1**'den **40**'a çıkıyor. Arama artık "bu işlemede girdi" demiyor, "bu kırk değişiklikten birinde girdi" diyor. Kalan iş aramanın dışında, işlemenin içinde, elle yapılacak. Takas eşit değildir — adım sayısı logaritmik düşerken yanıtın kabalığı doğrusal artıyor. On altı kat daha kaba bir yanıt için beş adım kazanılıyor. Bu, Dallanma ve İşbirliği kursunun sıkıştırma ölçümüyle aynı biçimin başka bir birimdeki görüntüsüdür: orada temizlenen tarihçenin **yanıtlayabildiği soru** azalıyordu, burada aranan tarihçenin **verebildiği yanıt** kabalaşıyor. İkisinin ortak sonucu şudur: aramanın çözünürlüğü arama anında değil, **işleme anında** belirlenir. Atomik işleme alışkanlığı bir üslup tercihi değil, ileride sorulacak sorunun çözünürlüğünü belirleyen bir karardır. ## Özet - Arama tek bir varsayıma dayanır: kusurun varlığı tarihçe boyunca bir kez değişir. Tekdüzelik bozulursa arama yanlış işlemeyi gösterir ve bunu haber vermez. - Tarihçe seksen kat büyürken doğrusal tarama **37** adımdan **3000** adıma çıkar, ikili arama **6**'dan **11**'e; bedel tarihçenin uzunluğundan değil, bir adımın dokunduğu kümeden gelir. - Doğrusal taramanın adımı kusurun tarihçedeki yerine eşittir; ikili aramanınki yere değil yalnızca uzunluğa bağlıdır ve aday kümesini **1/4000** çözünürlüğüne indirir. - Adım sayısı emeğin yarısıdır; diğer yarısı bir adımın süresidir ve onu belirleyen şey kâhinin otomatikleştirilebilmesidir. - Çatallanmış tarihçede aday kümesi bir sayı aralığı değil, iki uçtan erişilebilirlikle tanımlanan kümedir; adım sayısını o kümenin büyüklüğü belirler. - Değişiklikler kırklı gruplara toplandığında adım **11**'den **6**'ya iner ama yanıtın kapsamı **1**'den **40**'a çıkar; aramanın çözünürlüğü işleme anında belirlenir. ## Sonraki Adım İkili arama tarihçeye tek bir soru sorar ve yanıtı bir işleme olarak alır: kusur şurada girdi. Ama çoğu zaman sorulan soru bu değildir. Elde bir işleme yoktur, elde tek bir **satır** vardır ve sorulan şey o satırın oraya neden yazıldığıdır. Sonraki ders bu soruya bakar: bir satırın son yazarını bulmanın bedeli aynı tarihçede kaç adımdır, neden ikili aramanın adımıyla aynı biçimde büyümez, ve son yazarın gerçekten aranan kişi olmadığı durumda yanıt nereye kayar.