İkili Arama — Algoritma, Zaman Karmaşıklığı ve Kod

İkili arama, sıralı bir listede hedef bir değeri bulmanın hızlı bir yoludur. Ortadaki öğeyi kontrol eder, kalan değerlerin yarısını eler ve işlemi tekrarlarsınız. Liste sıralı değilse bu mantık geçerli olmaz.

Artan sıralı bir listede kural basittir: Ortadaki değer hedeften küçükse sağa bakın; büyükse sola bakın. Aralık her adımda yaklaşık yarıya indiği için ikili arama $O(\log n)$ zamanda çalışır.

İkili arama sıralı bir listede nasıl çalışır?

Şu sıralı listeyi kullanalım:

$$[3, 7, 12, 18, 24, 31, 39, 45, 52]$$

Hedefin $31$ olduğunu varsayalım.

Tam aralıkla başlayın. Ortadaki değer $24$'tür. $31 > 24$ olduğundan, $24$'ün solundaki her şey elenebilir. Bu yüzden arama şu aralıkta devam eder:

$$[31, 39, 45, 52]$$

Şimdi ortadaki değer $39$'dur. $31 < 39$ olduğundan, $39$'un sağındaki her şey elenebilir. Böylece aralık

$$[31]$$

olur.

Artık ortadaki değer $31$ olduğu için arama durur. Buradaki önemli fikir yalnızca hedefin bulunmuş olması değildir. İki karşılaştırmada aday aralık $9$ değerden $1$ değere düştü.

İkili arama neden $O(\log n)$'dir?

Her karşılaştırma kalan adayların yaklaşık yarısını eler. Bir adımdan sonra yaklaşık $n/2$ öğe kalır. İki adımdan sonra yaklaşık $n/4$ öğe kalır. $k$ adımdan sonra kalan boyut yaklaşık olarak

$$\frac{n}{2^k}$$

olur.

Bu miktar yaklaşık $1$ olduğunda arama biter. Dolayısıyla adım sayısı

$$2^k \approx n$$

koşulunu sağlar.

Her iki tarafın $\log_2$'si alınırsa

$$k \approx \log_2 n$$

elde edilir.

İkili aramanın iyi ölçeklenmesinin nedeni budur. Doğrusal arama en fazla $n$ kontrol gerektirebilir, ama ikili arama yalnızca aralığı sürekli yarıya indirmeye yetecek kadar kontrol gerektirir.

İkili arama kod örneği

Aşağıda Python'da standart bir yinelemeli sürüm verilmiştir: