ünite 4 · Diziler · ders 4.3

İkili arama

Sıralı listede ortadan böl: 1000 elemanda en fazla 10 adım.

9 dk 14 / 22

Sözlükte "kalem"i ararken ilk sayfadan başlamazsın: ortayı açarsın, k'den önce mi sonra mı diye bakıp yarısını atarsın. Bu ikili arama; tek şartı listenin sıralı olması.

Adımlar

sol ← 0, sağ ← uzunluk − 1
orta ← (sol + sağ) / 2 (tam bölme)
dizi[orta] aranan ise bitti
aranan daha küçükse sağ ← orta − 1, büyükse sol ← orta + 1
sol ≤ sağ olduğu sürece tekrarla; aşarsa yok

Neden bu kadar hızlı?

Her adım aday sayısını yarıya indirir: 1000 → 500 → 250 → … → 1. On adımda biter. Bir milyon elemanda yirmi adım. Doğrusal arama için bir milyon.

Sırasız diziyle ikili arama yanlış cevap verir, hata vermez. Önce sırala ya da sıralı olduğundan emin ol.

akış şeması elips: başla/bitir · dikdörtgen: işlem · paralelkenar: girdi/çıktı · baklava: karar

flowchart TD
  A[sol = 0, sağ = n-1] --> B{sol #lt;= sağ ?}
  B -- Hayır --> Y[/yok/]
  B -- Evet --> C[orta = sol+sağ / 2]
  C --> D{dizi#91;orta#93; = aranan ?}
  D -- Evet --> E[/orta yaz/]
  D -- Hayır --> F{aranan #lt; dizi#91;orta#93; ?}
  F -- Evet --> G[sağ = orta - 1]
  F -- Hayır --> H[sol = orta + 1]
  G --> B
  H --> B

sözde kod adımlar

1sol ← 02sağ ← uzunluk − 13İKEN sol ≤ sağ4  orta ← (sol + sağ) / 25  EĞER dizi[orta] = aranan İSE YAZ orta, DUR6  DEĞİLSE EĞER aranan < dizi[orta] İSE sağ ← orta − 17  DEĞİLSE sol ← orta + 18DÖNGÜ SONU9YAZ "yok"

aynısı C# ile C#

1int[] d = { 3, 8, 15, 21, 27, 34, 42, 50 };2int aranan = 34, sol = 0, sag = d.Length - 1, yer = -1;3while (sol <= sag)4{5    int orta = (sol + sag) / 2;6    if (d[orta] == aranan) { yer = orta; break; }7    if (aranan < d[orta]) sag = orta - 1; else sol = orta + 1;8}9Console.WriteLine(yer);

adım adım izleme

Kutuların her adımdaki değeri. Kağıtta izleme tablosu tutarken tam bunu yaparsın.

#	satır	sol	sağ	orta	d[orta]	not
1	sol=0, sağ=7 → orta=3	0	7	3	21	d[3]=21, 34 > 21 → sol = 4
2	sol=4, sağ=7 → orta=5	4	7	5	34	d[5]=34 → bulundu!

senin sıran

Aynı diziden 27'yi ve 10'u (yok) ara; her adımda sol/sağ/orta değerlerini tabloya yaz. "Yok" cevabına kaç adımda ulaştın?

Canlı Kod'da C# ile dene

kendini sına 1024 elemanlı sıralı dizide ikili arama en fazla kaç adım atar?

~10–11. 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1.

İşaret bu tarayıcıda kalır. XP için giriş yap — her ders +15 XP.

önceki dersDoğrusal arama sıradaki dersSıralama: kabarcık ve seçmeli