Algoritmaları
Bu derste oyunun haritası 🗺️
- Arama problemi — ne arıyoruz, “yok” nasıl denir? search problem
- Sıralı arama — baştan sona tek tek sequential search
- İkili arama — her adımda yarısını at binary search
- Oyunlarda ikili arama — XP tabloları, loot sandıkları, animasyon eğrileri
- İkiye bölme — hızlı mermi duvarın içinden neden geçer? bisection
- ⚙️ Perde arkası & ötesi — önbellek, enterpolasyon araması, sembol tabloları
…1 milyon kayıt içinde bir şeyi 20 adımda bulabilecek, bir loot sandığının nasıl çalıştığını ve hızlı bir merminin duvarı neden “ıskaladığını” açıklayabileceksiniz.
Kâğıttan bir sözlükte “kelebek” kelimesini
nasıl bulursunuz?
İlk sayfadan başlayıp kelimeleri tek tek mi okursunuz?
Tabii ki hayır! Ortalardan bir yerden açarsınız: “Burası m harfi, k daha önce” → sol yarıya geçersiniz…
Bu sezginin adı: ikili arama binary search. Bugün onu bir algoritmaya dönüştüreceğiz.
Peki sözlük sırasız olsaydı? 😱 O zaman tek yol baştan sona okumak: sıralı arama.
Oyunlarda arama her yerde
Mini sözlük (1/2)
| search | arama | Bir koleksiyonda aranan değeri bulmak |
| key | anahtar | Aradığımız değer (bir sayı, bir ad, bir ID…) |
| search hit / miss | başarılı / başarısız arama | Aranan bulundu / koleksiyonda yok |
| index | indeks | Elemanın dizideki sıra numarası (0’dan başlar) |
| sequential (linear) search | sıralı (doğrusal) arama | Baştan sona tek tek bakmak |
| binary search | ikili arama | Sıralı veride her adımda yarısını atmak |
| sorted | sıralı | Küçükten büyüğe dizilmiş (ikili aramanın ön koşulu!) |
Mini sözlük (2/2)
| invariant | değişmez | Döngü boyunca hep doğru kalan cümle |
| logarithm | logaritma | “Kaç kez ikiye bölebilirim?” sorusunun cevabı |
| sentinel | nöbetçi | Döngüyü kendiliğinden durduran, sona konan özel eleman |
| predicate | koşul fonksiyonu | Doğru/yanlış döndüren fonksiyon: “canı 20’den az mı?” |
| lower bound | alt sınır | Aranandan büyük ya da eşit olan ilk elemanın yeri |
| bisection | ikiye bölme | Bir aralığı yarıya bölerek bir sınırı bulmak |
| cumulative sum | kümülatif (birikimli) toplam | Her eleman = kendisine kadar olanların toplamı |
- arama problemi
- sıralı arama
- ikili arama
- oyunlarda ikili arama
- ikiye bölme (bisection)
- perde arkası & ötesi
Problem
Girdi: N elemanlı bir dizi a ve aranan bir anahtar key
Çıktı: key dizideyse indeksi, değilse “yok” işareti (genelde −1)
- Bulunursa: başarılı arama search hit
- Bulunamazsa: başarısız arama search miss
a[i] ile karşılaştırdığımızı sayacağız.a = [ 12, 45, 7, 88, 23 ] (envanterdeki eşya ID’leri)
search(a, 88)→ 3search(a, 50)→ −1
Neden −1? Çünkü geçerli indeksler 0, 1, 2… −1 hiçbir zaman gerçek bir indeks olamaz → “yok” demek için güvenli.
🎒 Ön bilgi: “bulunamadı” nasıl söylenir? return value
Fonksiyon bir değer döndürür (return); çağıran taraf bu değeri bir değişkene alıp kontrol eder.
−1: “indeks yok” işareti (C#, JS, kendi kodlarımız)None/null: “nesne yok” (bir düşman, bir eşya ararken)- Hata fırlatmak exception: Python’un
list.index’i bulamazsa programı durdurur!
a[search(a, 50)] → a[-1]! Python’da bu son eleman demektir: hata bile vermez, yanlış eşyayı verir. 😱- arama problemi
- sıralı arama
- ikili arama
- oyunlarda ikili arama
- ikiye bölme (bisection)
- perde arkası & ötesi
Fikir: baştan sona tek tek bak
- i = 0’dan başla.
a[i]aranan mı? Evetse i’yi döndür.- Değilse bir sonrakine geç.
- Dizi bittiyse −1 döndür.
Sıralı arama — animasyon (sırasız dizi)
Kaç karşılaştırma? 📐
- En iyi best case: aranan ilk elemanda → 1
- En kötü worst case: aranan sonda ya da hiç yok → N
- Ortalama (bulunan anahtar her konumda eşit olasılıkla):
\( \dfrac{1 + 2 + \dots + N}{N} = \dfrac{N(N+1)/2}{N} = \dfrac{N+1}{2} \sim \dfrac{N}{2} \)
1’den N’e kadar toplam = \( N(N+1)/2 \) (Gauss’un küçükken bulduğu söylenen formül).
Yani süre N ile doğru orantılı: N iki katına çıkarsa süre de iki katına çıkar. Buna doğrusal linear zaman denir.
🔗 Başka gözle: etkileşimli anlatımlar ve yazılar
Aynı konuyu başka bir anlatımla, kendi elinizle oynayarak görmek çok işe yarar. Kartlar yeni sekmede açılır; çoğu İngilizce ama görsel ve etkileşimli.
Hazır fonksiyonlar da sıralı arama yapar!
| dil | “var mı?” | “nerede?” | koşulla bul |
|---|---|---|---|
| Python | x in liste | liste.index(x) | for + if · next(...) |
| C# | list.Contains(x) | list.IndexOf(x) | list.Find(...) |
| JavaScript | arr.includes(x) | arr.indexOf(x) | arr.find(...) |
for döngüsüdür: N karşılaştırma. Oyunda Update() içinde (saniyede 60 kez) 1000 düşmanlık bir listede Contains çağırmak = saniyede 60.000 karşılaştırma… ve her düşman bunu yapıyorsa 60 milyon!🎒 Ön bilgi: koşulla arama — geleneksel ve modern predicate
“Canı 20’den az olan ilk düşmanı bul.” Aranan bir değer değil, bir koşul. (enemies: düşman nesnelerinin listesi; her düşmanın hp alanı var.)
Doğru/yanlış döndüren küçük fonksiyona koşul fonksiyonu predicate denir. Modern yazımda bunu lambda / ok fonksiyonu olarak veririz. İkisi de aynı işi yapar: sıralı arama.
⚙️ Nöbetçi hilesi sentinel
Normal sıralı aramada döngü her adımda iki soru sorar:
i < Nmi? (dizi bitti mi?)a[i] == keymi?
Hile: aranan değeri dizinin sonuna ekle. Artık döngü mutlaka durur → 1. soruya gerek yok!
Döngü bitince tek bir kontrol: durduğumuz yer nöbetçinin kendisi mi?
Klasik bir optimizasyon (Knuth’un kitaplarında da var). Modern işlemcilerde kazanç küçüktür; ama “iç döngüden gereksiz kontrolü çıkar” fikri her yerde işe yarar.
⚙️ Nöbetçili sıralı arama — kod
🎒 C#’taki koşul ? x : y: “koşul doğruysa x, değilse y” (üçlü ifade ternary operator). Altındaki yorumda geleneksel if/else hali var.
🎮 Sık arananı öne al move-to-front
Oyuncunun büyü kitabında 200 büyü var ama savaşta hep aynı 5’ini kullanıyor.
Fikir: bir büyü bulunduğunda onu listenin başına taşı. Sık kullanılanlar hep önde durur → sıralı arama çoğu zaman 1–5 adımda biter.
Buna “kendini düzenleyen liste” self-organizing list denir. Aynı fikir: “son kullanılan dosyalar”, tarayıcı geçmişi, işlemci önbelleklerinin LRU politikası.
| arama | liste (önce → sonra) | adım |
|---|---|---|
| — | Ateş · Buz · Şimşek · İyileş · Kalkan | |
| İyileş | İyileş · Ateş · Buz · Şimşek · Kalkan | 4 |
| İyileş | İyileş · Ateş · Buz · Şimşek · Kalkan | 1 |
| Kalkan | Kalkan · İyileş · Ateş · Buz · Şimşek | 5 |
| İyileş | İyileş · Kalkan · Ateş · Buz · Şimşek | 2 |
a[mid]’e tek adımda atlayabilmeye dayanır (rastgele erişim random access). Dizide bu bir adres hesabıdır; bağlı listede ise ortadaki düğüme ulaşmak için N/2 düğüm yürümek gerekir → her “zıplama” zaten sıralı arama kadar pahalı.- arama problemi
- sıralı arama
- ikili arama
- oyunlarda ikili arama
- ikiye bölme (bisection)
- perde arkası & ötesi
Aklınızdan dünyadaki herhangi bir insanı tutun.
Ben sadece evet/hayır soruları soracağım.
Kaç soruda bulabilirim? 100? 1000? 1 milyon?
Her soru adayları yarıya indirirse: 2³³ ≈ 8,6 milyar ≥ dünya nüfusu → 33 soru yeter!
“Akinator” adlı ünlü oyun, aklınızdaki karakteri genellikle 20 civarı soruda bulur. Bu bölümün sihirli kelimesi: logaritma.
Fikir: ortadakine bak, yarısını at
- Aralık: tüm dizi,
lo = 0,hi = N − 1 - Ortadaki elemana bak:
mid - Aranan küçükse → sol yarıda devam:
hi = mid − 1 - Aranan büyükse → sağ yarıda devam:
lo = mid + 1 - Eşitse → bulundu! Aralık boşalırsa (
lo > hi) → yok
Skor tablosunda 63’ü arıyoruz: 15 eleman, 4 adım. Turuncu = mid, soluk = atılan yarı.
- Dizi sıralı olmalı.
a[mid]’e tek adımda erişebilmeliyiz (dizi ✔, bağlı liste ✘).
İkili arama — animasyon
İz tablosu trace — başarılı arama: P
İz tablosu — başarısız arama: Q
lo, Q’nun eklenmesi gereken yeri gösterir — birazdan çok işimize yarayacak!🎒 Ön bilgi: tam sayı bölmesi integer division
mid bir indeks olduğu için tam sayı olmalı. Ama her dilde / farklı davranır:
| dil | 7 / 2 | tam sayı bölmesi | dikkat! |
|---|---|---|---|
| Python | 3.5 | 7 // 2 → 3 | a[7 / 2] → ❌ TypeError: list indices must be integers |
| C# | 3 (iki int → tam sayı!) | 7 / 2 → 3 | 7.0 / 2 → 3.5 · (float)7 / 2 → 3.5 |
| JavaScript | 3.5 | Math.floor(7 / 2) → 3 | a[3.5] → undefined (hata bile yok! 😱) |
C# öğrencilerinin klasik hatası: int can = 7; float oran = can / 2; → 3 (3.5 değil), çünkü bölme önce tam sayı olarak yapılır.
İkili arama — kod
Neden (lo + hi) / 2 değil de lo + (hi − lo) / 2? → Birkaç slayt sonra, 9 yıl saklı kalan bir hata hikâyesi. 🕵️
Neden doğru çalışıyor? Değişmez invariant
key dizideyse, mutlaka a[lo…hi] aralığındadır.”- Başta doğru: aralık tüm dizi.
- Her adımda korunur:
key < a[mid]ise dizi sıralı olduğundan mid ve sağındakilerin hepsi key’den büyük → atmak güvenli. - Sonda: aralık boşaldıysa (
lo > hi), key hiçbir yerde olamaz → −1 doğru cevap. ✔
Özyinelemeli ikili arama recursive
“Yarıda ara” cümlesi aslında: aynı problemi daha küçük bir aralıkta çöz → özyineleme!
- Temel durum base case: aralık boş → −1
- Her çağrı, yığına stack bir kare ekler (yığınlar dersi!)
- Derinlik en fazla ~lg N → 1 milyar elemanda bile ~30 kare. Güvenli. ✔
📐 Kaç karşılaştırma? Logaritma logarithm
Kanıt fikri: her karşılaştırma aday sayısını en az yarıya indirir: N → N/2 → N/4 → … → 1.
\( \lg N = \log_2 N \) = N’i kaç kez yarıya bölebilirsin?
🎮 Sayı tahmin oyunu
Bilgisayar modunda 1–100 arası bir sayı tutun ve dürüst cevap verin. Bilgisayar ikili arama yapıyor: en fazla 7 tahminde bulur, çünkü \( 2^7 = 128 \ge 100 \).
N büyüdükçe: sıralı arama vs ikili arama 📈
🎬 Ara: ikili arama, 2 dakikada
Binary Search Algorithm in 100 Seconds
Fireship · 2 dk 20 sn · YouTube’da aç
Sayı tahmin oyunundaki “ortadan böl” fikrinin kodla birlikte hızlı özeti; lo, hi ve mid’in nasıl güncellendiğini izleyin.
while (lo <= hi) yerine while (lo < hi) yazarsak ne olur?lo == hi) döngü o elemana hiç bakmadan biter. Örn. [7] dizisinde 7’yi ararsak hemen −1 döner. Bu tür “bir eksik/bir fazla” hatalarına off-by-one hatası denir. Kod laboratuvarında deneyin!mid = lo + (hi - lo) / 2 yerine mid = lo yazarsak ne olur?lo = mid + 1. Değişmez korunduğu için sonuç doğrudur, ama aday kümesi yarıya değil birer birer azalır → N karşılaştırma. “Yarıya bölmek” hızın kaynağıdır, doğruluğun değil.📜 Basit görünen, yazması zor bir algoritma
mid = (lo + hi) / 2int 32 bittir: en büyük değer 2.147.483.647. Bir fazlası en küçük negatif sayıya “sarar”. Oyunlarda da çok görülür (efsane: Civilization’daki “nükleer Gandhi”).🧪 Kod laboratuvarı: ikili arama (otomatik testli)
- 6. satırda
<=yerine<yaz. Hangi test başarısız oldu? - 9. satırda
hi = mid - 1yerinehi = midyaz. Ne oldu, neden? - 7. satırı
const mid = lo;yap. Testler geçiyor mu? Okuma sayısı ne diyor? - Kendi sıralı arama fonksiyonunu yaz: testler geçer mi, uyarı çıkar mı?
🐍 Aynı laboratuvar — Python
- 7. satırda
//yerine/yaz. Hata mesajını oku: neden? return -1satırını sil. Python bulamayınca ne döndürüyor?- Özyinelemeli sürümü yaz (önceki slayttaki gibi,
lovehiparametreli bir yardımcı fonksiyonla).
⚙️ Küçük dizilerde sıralı arama daha hızlı olabilir!
Karşılaştırma sayısı her şey değildir. Donanım da önemli:
- Önbellek cache: işlemci bellekten 64 baytlık bloklar (önbellek satırı) getirir = 16 tane
int. Sıralı arama bu blokları sırayla okur → çok hızlı. İkili arama bellekte zıplar → büyük dizilerde her zıplama bir önbellek ıskası. - Dal tahmini branch prediction: sıralı aramanın
if’i neredeyse hep “hayır” → işlemci kolayca tahmin eder. İkili aramanın sol/sağ kararı ise yazı-tura gibi → sık yanılır.
Birkaç düzine elemana kadar düz sıralı arama genelde ikili aramayı geçer. Hızlı kütüphaneler bu yüzden önce ikili aramayla aralığı daraltıp, küçük kalan kısımda sıralı aramaya geçer.
Ders: “Büyük-O” büyük N için doğrudur; küçük N’de sabitler ve donanım kazanır. Ölçmeden karar vermeyin (algoritma analizi dersindeki bilimsel yöntem!).
- arama problemi
- sıralı arama
- ikili arama
- oyunlarda ikili arama
- ikiye bölme (bisection)
- perde arkası & ötesi
Aranan yoksa: “nereye eklenirdi?” lower bound · rank
Çoğu zaman tam eşitlik değil, sınır ararız:
- lower bound:
a[i] ≥ keyolan ilk i - = key’den küçük kaç eleman var? (rank)
- = key sıralı diziye nereye eklenmeli?
🎮 Skor tablosu: yeni skor 1530 → kaçıncı sıraya girer?
Fark: aralık “yarı açık” [lo, hi); döngü lo < hi; eşit bulunca durmadan sola devam ederiz. Sonunda lo = cevap.
a = [1, 3, 3, 3, 5] dizisinde 3 aranıyor. Klasik ikili arama ve lower_bound hangi indeksleri döndürür?🎮 XP → seviye tablosu
Kutular: her seviyenin başladığı XP eşiği (sıralı!). Aranan: eşiği oyuncunun XP’sini geçmeyen en büyük eşik (floor). 16 seviyede en fazla 5 adım; 1000 seviyelik bir MMO’da bile 10 adım.
🎁 Loot tablosu nasıl çalışır? weighted random
Ağırlıklar: Sıradan 60 · Nadir 28 · Epik 10 · Efsanevi 2
- Kümülatif toplam cumulative sum al:
[60, 88, 98, 100] - 0 ile 100 arası rastgele bir
rçek: ör.r = 93.4 r’den büyük ilk kümülatif değeri ikili aramayla bul: 98 → indeks 2 → Epik!
Neden doğru? r’nin her aralığa düşme olasılığı, o aralığın genişliği ile orantılı: [88, 98) aralığı 10 birim → %10.
🎁 Canlı demo: sandık açalım
🎞️ Animasyon eğrileri: zamanı hangi kareler arasında?
Bir animasyon eğrisi, zamana göre sıralı anahtar karelerden keyframes oluşur: (0 sn → 0), (0,5 sn → 2), (1,2 sn → 1)…
t = 0,8 sn’deki değer? → t’yi çevreleyen iki kareyi ikili aramayla bul, aralarında doğrusal enterpolasyon yap.
Unity’nin AnimationCurve.Evaluate, Godot’nun Curve’ü ve her animasyon sistemi bunu yapar — her karede, her kemik için!
lerp(a, b, t) = a + (b − a) · t → t = 0’da a, t = 1’de b, aradaki değerlerde ikisinin arası. Oyun programlamanın en çok kullanılan formülü.Hazır ikili arama fonksiyonları
~Bulunamazsa Array.BinarySearch “eklenmesi gereken yer”i bit tersine çevirip negatif bir sayı olarak döndürür (−1 ile karışmasın diye). ~j bunu geri çevirir. Kural: sonuç negatifse yok, ~sonuç = ekleme yeri.🧪 Kod laboratuvarı: lower bound’u kendin yaz
[lo, hi) yap (hi = a.length) · döngü lo < hi · a[mid] < key ise lo = mid + 1, değilse hi = mid · sonunda lo döndür. Takılırsan “lower bound” slaytına bak.- arama problemi
- sıralı arama
- ikili arama
- oyunlarda ikili arama
- ikiye bölme (bisection)
- perde arkası & ötesi
Fikir: “evet/hayır” sorusu bir noktada değişiyorsa
İkili arama sadece dizilerde çalışmaz. Bir soru düşünün: cevabı bir noktaya kadar hep hayır, sonra hep evet olsun:
✘ ✘ ✘ ✘ ✘ ✘ ✔ ✔ ✔ ✔ ✔
Böyle bir koşula monoton monotonic denir. Sınırı ikili aramayla buluruz: ortaya bak, ✘ ise sağa, ✔ ise sola.
Aralık sürekli bile olabilir (zaman, mesafe, açı…): her adımda aralık yarıya iner → 20 adımda milyonda bir hassasiyet.
- Mermi t anında duvara değmiş mi?
- Zıplama gücü h ile platforma yetişiliyor mu?
- Kaçıncı sürümde oyun çökmeye başladı?
- Zorluk d’de test oyuncularının yarısından fazlası kaybediyor mu?
💥 Hızlı mermi neden duvarın içinden geçer? tunneling
İkiye bölme — kod
🎒 cond bir fonksiyon parametresidir: “sorulacak soruyu” dışarıdan veririz (callback · predicate). Aynı first_true her türlü “ne zaman/ne kadar?” sorusu için çalışır.
📜 Hangi sürümde bozuldu? git bisect
Oyununuz dün akşam akıcıydı, bugün 20 FPS. Aradaki 500 değişiklikten (commit) hangisi bozdu?
- Sırayla tek tek denemek: 500 derleme + test 😩
- İkiye bölme: ortadaki sürümü dene → iyi mi kötü mü? → yarısını at… ~9 deneme (\( 2^9 = 512 \))
Git bunu hazır bir komut olarak sunar: git bisect. Siz sadece “iyi” ya da “kötü” dersiniz; ortadaki sürüme Git atlar.
- arama problemi
- sıralı arama
- ikili arama
- oyunlarda ikili arama
- ikiye bölme (bisection)
- perde arkası & ötesi
Telefon rehberi gibi: enterpolasyon araması interpolation search
Rehberde “Zeynep”i ararken ortadan açmazsınız: sonlara yakın bir yerden açarsınız!
Fikir: aranan değerin aralıktaki oranına göre tahmin yap:
\( pos = lo + \dfrac{key - a[lo]}{a[hi] - a[lo]} \cdot (hi - lo) \)
- Veriler düzgün dağılmışsa: ~\( \lg \lg N \) adım — 1 milyar elemanda ~5 adım!
- Ama veriler dengesizse (ör.
1, 2, 3, 4, 1000000): en kötü N adım 😬
Sonu bilinmeyen dizide: üstel arama exponential (galloping) search
Dizinin boyutunu bilmiyorsak (çok uzun bir kayıt, sürekli büyüyen bir liste) ya da aranan başa yakınsa:
- 1., 2., 4., 8., 16.… elemanlara bak (her seferinde iki katı).
- Aranandan büyük bir eleman bulunca dur: aranan son iki bakış arasında.
- O aralıkta ikili arama yap.
Toplam ~2 lg k adım (k = aranan elemanın konumu). Baştaki elemanlar için çok hızlı!
Sıralı dizi bir “sözlük” olabilir mi? symbol table
Oyunda anahtar → değer saklamak isteriz: eşya adı → adet, oyuncu ID → profil…
Anahtarları sıralı dizide tutarsak get ikili arama ile hızlı. Peki ekleme?
Yeni anahtarın yerini lg N’de buluruz ama ondan büyük herkesi bir sağa kaydırmak gerekir → ortalama N/2 taşıma.
| yapı | arama | ekleme |
|---|---|---|
| sırasız dizi / liste | N | 1 |
| sıralı dizi | lg N | N |
| ❓ ikisinin de iyi yanı | lg N | lg N |
İkili arama ağaçları (BST): ikili aramanın “ortadakine bak, sola/sağa git” fikrini bir ağaca dönüştürür → arama ve ekleme ~lg N. Ağaçlar sunumu ▶
Hash tabloları: ortalama sabit zaman — ama sırayı kaybeder.
Özet tablo 📋
| yöntem | ön koşul | en iyi | ortalama | en kötü |
|---|---|---|---|---|
| sıralı arama | — (her yerde) | 1 | N/2 (bulunursa) | N |
| ikili arama | sıralı + rastgele erişim | 1 | ~lg N | ⌊lg N⌋ + 1 |
| enterpolasyon araması | sıralı + düzgün dağılım | 1 | ~lg lg N | N |
| üstel arama | sıralı (boyut bilinmese de) | 1 | ~2 lg k (k = konum) | |
| ikiye bölme | monoton koşul | hassasiyet ε için ~lg(aralık / ε) adım | ||
Değerler karşılaştırma sayısıdır.
Derin hikâye: “Nükleer Gandhi” — bir taşma efsanesi
- Efsane: İlk Civilization’da (1991) barışçıl Gandhi’nin saldırganlık değeri en düşük, 1’di. Demokrasiye geçen ülkelerin saldırganlığı 2 azalıyordu; 1 − 2 = −1, işaretsiz 8 bitlik bir sayıda 255’e sarıyor ve Gandhi bir anda oyunun en saldırgan, nükleer silah kullanan lideri oluyordu.
- Gerçek: Bu anlatı ilk kez 2012’de TV Tropes vikisine kanıtsız eklendi ve yayıldı. Civilization V’te (2010) Gandhi’nin nükleer silah kullanma eğilimi gerçekten yüksek ayarlanmıştı; efsanenin buradan beslenmiş olması muhtemel. Serinin yaratıcısı Sid Meier 2020’deki anı kitabında bu hatanın ilk oyunda mümkün olmadığını açıkladı.
- Durum: Nükleer Gandhi → efsane. Tamsayı taşması → çok gerçek: Joshua Bloch 2006’da, Java’nın standart ikili aramasındaki
(low + high) / 2satırının çok büyük dizilerde taşıp negatif indeks ürettiğini ve hatanın JDK’da yaklaşık dokuz yıl fark edilmediğini yazdı. Aynı hata birçok kitapta ve mergesort uygulamasında da vardı.
low + (high − low) / 2 ile hesaplayın; oyunda can, para, saldırganlık gibi değerleri sınırlayın (clamp).Kaynak: Wikipedia: Nuclear Gandhi · Bloch 2006 (Google Research)
🧰 Kütüphaneler ve araçlar
| ad | platform | ne yapar / sınırları | nasıl eklenir |
|---|---|---|---|
| Array.BinarySearch · List<T>.BinarySearch | C# / Unity | Bulamazsa negatif sayı döner: ~sonuç eklenecek yerin indeksidir. | yerleşik |
| bisect | Python | bisect_left, bisect_right, insort; 3.10’dan beri key=. | standart kütüphane |
| std::lower_bound · upper_bound · equal_range | C++ | Sıralı aralıkta ilk ≥ / ilk > konum. | #include <algorithm> |
| lodash sortedIndex | JavaScript | JS’te yerleşik ikili arama yok; sıralı dizide ekleme yeri. | npm install lodash |
🧩 Oyunlarda ikili arama
- Ağırlıklı ganimet tablosu: ağırlıkların önek toplamlarını tutun, [0, toplam) aralığında rastgele bir sayı seçin, ikili aramayla hangi eşyaya düştüğünü bulun: her çekiliş O(log n).
- Deneyim → seviye: kümülatif XP tablosunda oyuncunun seviyesini bulmak.
- Animasyon/eğri anahtar kareleri: t anına en yakın iki anahtar kare.
- Cevap üzerinde ikili arama: “düşmanın canı en az ne olmalı ki oyuncu 3 vuruşta öldüremesin?” gibi tekdüze sorular.
- Orta nokta taşması (yukarıdaki hikâye).
- Sonsuz döngü:
lo = midilelo < hibirlikteyse. - Sıralı olmayan veride ikili arama.
- C#’ta negatif dönüşü indeks sanmak.
🤖 Bu konuyu bir YZ kod asistanıyla yazarken
- (lo + hi) / 2 taşması
- Bir fazla/eksik sınır hatası ve sonsuz döngü
- BinarySearch’ün negatif dönüşünü indeks sanmak
- Sıralanmamış listede arama
“Unity 6, C#. Ağırlıklı ganimet tablosu yaz: LootTable
- Aralığın yarı açık mı ([lo, hi)) kapalı mı olduğunu yazdırın
- Orta noktayı taşmasız isteyin
- Sınır durumlarını (boş, tek, hepsi eşit, bulunamadı) test ettirin
- Standart fonksiyon (bisect, BinarySearch) alternatifini sorun
🚀 Proje ve araştırma önerileri
- [kolay] Ganimet tablosu — Önek toplamı + ikili arama; 1 milyon çekilişte histogramı ağırlıklarla karşılaştırın.
- [kolay] XP eğrisi — Seviye tablosunu üretin ve XP’den seviyeyi ikili aramayla bulun.
- [orta] Cevap üzerinde ikili arama — Bir düşmanın “adil” can değerini simülasyon + ikili aramayla otomatik ayarlayın.
- [araştırma] Taşma avı — Kendi oyununuzdaki sayısal değerlerde taşma riskini tarayan küçük bir statik kontrol ya da test yazın.
📄 Akademik okumalar ve kaynaklar
Dokuz yıl gizli kalan taşma.
Profesyonellerin bile ikili aramayı doğru yazmakta zorlandığı deney.
İkili aramanın tarihi ve çeşitleri.
Neler öğrendik? 🎒
- Arama problemi: indeks ya da −1; başarılı / başarısız arama.
- Sıralı arama: her yerde çalışır, N adım; hazır fonksiyonlar da böyle!
- Nöbetçi, öne alma: küçük ama akıllı hileler.
- İkili arama: sıralı dizi + ortadan bölme → ⌊lg N⌋ + 1.
- Logaritma = “kaç kez yarıya?” · \( 2^{10} \approx 1000 \).
- lower bound: “nereye eklenirdi?” — XP tabloları, loot sandıkları, animasyon eğrileri.
- İkiye bölme: monoton koşul → çarpışma anı,
git bisect. - ⚙️ Taşma hatası, tam sayı bölmesi, önbellek ve dal tahmini.
Alıştırmalar 🏋️
- Kâğıt-kalem:
A E I K M O P R S T Udizisinde I ve Z için ikili aramanın iz tablosunu (lo, hi, mid) çıkarın. - Kod laboratuvarında upper bound’u (key’den büyük ilk eleman) yazın. lower bound ile farkı nedir?
- “Bir sayının dizide kaç kez geçtiğini” lg N zamanda bulun. (İpucu: upper bound − lower bound.)
- p5.js’te bir loot sandığı yapın: ağırlıklar bir dizide, tıklayınca sandık açılsın ve çıkan eşya ekranda görünsün. 1000 kez açıp yüzdeleri yazdırın.
- Unity’de hızlı bir mermi (Rigidbody) duvara ateşleyin. Collision Detection: Discrete ↔ Continuous farkını gözlemleyin.
- 🤖 Bir YZ asistanından ikili arama yazmasını isteyin. Değişmezi kontrol edin;
[7],[]ve tekrar eden elemanlarla test edin.
🎮 Bu sunumdaki oyunlar
Adı geçen oyunu tanımıyorsanız: oyuncuların kullandığı wiki sayfası ve oyunu kısaca gösteren bir video. ▶ video slaydın üstünde açılır (Esc ile kapanır); 🎯 işaretli bağlantılar doğrudan bu sunumdaki konuya gider.
Kaynaklar: videolar 🎬
Linear SearchCS50 Shorts (Harvard)
Binary SearchCS50 Shorts (Harvard)
Binary search in 4 minutesMichael Sambol
What is binary searchmycodeschool
Algorithms: Binary SearchHackerRank (Gayle Laakmann McDowell)
Binary Search Algorithm in 100 SecondsFireship
Binary Search — A Different PerspectivemCoding (Python)