İkili arama

İkili arama, sözlükte bir kelimeyi aramanın yoludur: sözlüğü ortadan açın, kelimenin önce mi sonra mı geldiğine bakın ve o yarıyla tekrarlayın. Sıralı bir listede bir milyon değer arasından herhangi birini en fazla 20 karşılaştırmada bulur.

Ortadaki çubuğu vurgulanmış, yarısı soluklaşmış ve aranan değerin yüksekliğinde kesikli bir çizgi bulunan sıralı bir çubuk dizisi
Ortadaki çubuğu vurgulanmış, yarısı soluklaşmış ve aranan değerin yüksekliğinde kesikli bir çizgi bulunan sıralı bir çubuk dizisi

Temel fikir

Sıralı bir listede tek bir karşılaştırma, aranan değeri bulup bulmadığınızdan fazlasını söyler: değerin hangi tarafta olduğunu da söyler. Aranan değeri ortadaki değerle karşılaştırın. Eşitlerse işiniz biter. Ortadaki değer daha küçükse ondan öncekilerin hepsi de daha küçüktür, bu yüzden aranan değer ancak ondan sonra olabilir. Daha büyükse aranan değer ancak ondan önce olabilir. Yalnızca o yarıyı tutun ve tekrarlayın.

Bir örnek

2, 5, 8, 12, 16, 23, 38, 56, 72, 91 listesinde 23'ü arayın. Ortadaki değer 16, daha küçük, bu yüzden yalnızca 23 ile 91 arası kalır. Bunların ortası 56, daha büyük, bu yüzden yalnızca 23 ve 38 kalır. Bunların ortası 23: 3 karşılaştırmadan sonra 6. sırada bulundu; doğrusal arama 6 karşılaştırma gerektirir. Aynı listede 40'ı aramak 16, 56, 23 ve 38'i karşılaştırır, ardından hiçbir şey kalmaz: 40'ın listede olmadığını anlamak için 4 karşılaştırma, doğrusal aramada ise 10.

Yarıya indirmenin gücü

Bir karşılaştırmadan sonra listenin en fazla yarısı, ikisinden sonra dörtte biri, k karşılaştırmadan sonra en fazla yaklaşık n/2ᵏ kadarı kalır. Arama hiçbir şey kalmadığında durur, bu yüzden en fazla ⌊log₂ n⌋ + 1 karşılaştırma gerektirir: 40 değer için 6, 1.000 için 10, bir milyon için 20 ve bir milyar için 30. Listeyi iki katına çıkarmak yalnızca bir karşılaştırma ekler. Bu, O(log n) diye yazılır.

Anlatması kolay, doğru yazması zor

John Mauchly ikili aramayı 1946'da tanımladı, ancak Donald Knuth'a göre her liste uzunluğunda çalışan ilk sürüm ancak 1962'de yayımlandı. Jon Bentley daha sonra profesyonel programcıların yalnızca yaklaşık onda birinin onu doğru yazdığını gördü: bitiş koşulları ve yarılar bölünürken eklenen ya da çıkarılan bir kolayca yanlış yapılır. 2006'da Joshua Bloch, ortayı bulmanın yaygın yolunun, yani (low + high) / 2 ifadesinin, çok uzun listelerde taşma (overflow) yapabileceğini gösterdi; bu hata Java kitaplığında yıllarca durmuştu. Uygulamanın yaptığı gibi low + (high − low) / 2 yazmak bunu önler.

John Mauchly (soldan beşinci), ENIAC’ın önünde diğer ENIAC yetkilileriyle birlikte, ABD Ordusu’na ait bir fotoğrafta. Mauchly ikili aramayı 1946’da tanımladı.
John Mauchly (soldan beşinci), ENIAC’ın önünde diğer ENIAC yetkilileriyle birlikte, ABD Ordusu’na ait bir fotoğrafta. Mauchly ikili aramayı 1946’da tanımladı.

Türler ve kullanım alanları

Aynı değerden birkaç tane varsa ikili arama eşleşmelerden birini bulur; sola ya da sağa devam eden sürümler ilkini ya da sonuncusunu, ya da eksik bir değerin ekleneceği yeri bulur. Aynı yarıya indirme fikri bir denklemin kökünü (ikiye bölme yöntemi), bir hatanın ilk ortaya çıktığı sürümü (git bisect) ve birçok optimizasyon bulmacasının cevabını bulur. İkili arama ağaçları verileri, her arama aynı yarıya indirme yolunu izleyecek şekilde saklar.

Kendiniz deneyin

Uygulamayı açın, Aranan değer alanında bir değer seçin ve Adım'a basın. Gölgeli bölüm aranan değerin hâlâ bulunabileceği yerdir; ortadaki değer vurgulanır ve elenen yarı soluklaşır. Kutucuklar kaç değerin hâlâ olası olduğunu ve doğrusal aramanın aynı değer için kaç karşılaştırma gerektireceğini gösterir. Farkın büyüdüğünü görmek için listede olmayan bir değeri arayın ya da 40 çubuk kullanın.

Sık sorulan sorular

İkili aramanın zaman karmaşıklığı nedir?

O(log n): n değer için en fazla ⌊log₂ n⌋ + 1 karşılaştırma. En iyi durumda, aranan değer ortadaysa, tek karşılaştırma yeter. Yinelemeli sürüm O(1) ek bellek gerektirir.

İkili arama ile doğrusal arama arasındaki fark nedir?

Doğrusal arama her değeri sırayla kontrol eder ve her listede çalışır, ama n karşılaştırma gerektirebilir. İkili arama yalnızca sıralı bir listede çalışır, ama her karşılaştırmada kalanın yarısını eler, bu yüzden yaklaşık log₂ n karşılaştırma gerektirir.

Yalnızca ikili arama kullanmak için bir listeyi sıralamaya değer mi?

Ancak listede çok kez arama yapacaksanız. Sıralama yaklaşık n log n adım sürer, bu da tek bir doğrusal aramadan fazladır. Liste bir kez sıralandıktan sonra her arama çok ucuzdur.

İkili arama listeler dışında başka şeylerde de çalışır mı?

Evet, bir testin cevabın hangi tarafında olduğunuzu söylediği her şeyde: bir sayı aralığında, bir programın sürümlerinde ya da bir büyük-küçük tahmin oyunundaki tahminlerde.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

İkili aramayı deneyin