9. 1000 elemanlı sıralı bir kümede en kötü durumda İkili Arama kaç karşılaştırma yapar?
A) 10Bu soruda, sıralı bir kümede İkili Arama (Binary Search) algoritmasının en kötü durumda kaç karşılaştırma yapacağını bulmamız isteniyor. İkili Arama, bilgisayar bilimlerinde çok temel ve önemli bir arama algoritmasıdır. Şimdi adım adım bu soruyu çözelim:
İkili Arama, sadece sıralı (küçükten büyüğe veya büyükten küçüğe dizilmiş) kümelerde çalışan bir arama algoritmasıdır. Çalışma prensibi oldukça basittir: Her adımda arama yapılan kümenin tam ortasındaki elemanla aranan elemanı karşılaştırırız. Eğer aranan eleman ortadaki elemandan küçükse, aramanın sol yarısında devam ederiz; büyükse sağ yarısında devam ederiz. Bu şekilde her adımda arama uzayını yarıya indiririz.
Bir algoritmanın "en kötü durumu", algoritmanın çalışması için gereken sürenin (veya bu durumda karşılaştırma sayısının) maksimum olduğu senaryodur. İkili Arama için en kötü durum, aranan elemanın kümede olmaması veya aranan elemanın, arama uzayı tek bir elemana düşene kadar bulunamamasıdır. Bu durumda algoritma, arama uzayı tamamen tükenene kadar karşılaştırma yapmaya devam eder.
İkili Arama her adımda arama uzayını yarıya indirdiği için, karşılaştırma sayısı logaritmik bir ilişkiyle bulunur. $N$ elemanlı bir kümede en kötü durumda yapılan karşılaştırma sayısı genellikle $\lfloor \log_2 N \rfloor + 1$ formülü ile ifade edilir. Burada $\log_2 N$, $N$ sayısını 2'nin kaçıncı kuvveti olarak yazabileceğimizi gösterir. $\lfloor \dots \rfloor$ sembolü ise "taban fonksiyonu" olup, içindeki sayının tam kısmını alır (örneğin, $\lfloor 9.96 \rfloor = 9$). +1 ise, son karşılaştırmayı temsil eder (yani arama uzayı tek elemana düştüğünde yapılan karşılaştırma).
Şimdi $N = 1000$ eleman için bu formülü uygulayalım:
Öncelikle $\log_2 1000$ değerini bulalım:
$2^9 = 512$
$2^{10} = 1024$
Görüldüğü gibi, 1000 sayısı $2^9$ ile $2^{10}$ arasındadır. Yani $\log_2 1000$ değeri 9 ile 10 arasındadır (yaklaşık 9.965).
Şimdi formülümüzü kullanalım:
En kötü durum karşılaştırma sayısı $= \lfloor \log_2 1000 \rfloor + 1$
$= \lfloor 9.965... \rfloor + 1$
$= 9 + 1$
$= 10$
Bu, 1000 elemanlı bir kümede İkili Arama'nın en kötü durumda maksimum 10 karşılaştırma yapacağı anlamına gelir. Her karşılaştırmada arama uzayı yarıya iner ve 10 adımda 1000 elemanlık bir küme tek bir elemana kadar indirgenebilir.
Cevap A seçeneğidir.
