İkili arama

Sıralı bir dizide bir değeri, ortaya bakıp değerin olamayacağı yarıyı atarak bulur. Her karşılaştırma kalanı yarıya indirir.

en iyi Ω(1)
ortalama Θ(log n)
en kötü O(log n)
bellek O(1)

Bunlar ne demek?

Sıralı: artan düzende. İkili arama buna ihtiyaç duyar; sırasız veride yanlış cevap verir.
Yarıya bölme: her karşılaştırma kalanın yarısını, hedefin olamayacağı yarıyı atar.
log₂ n: n, 1 kalana kadar kaç kez yarıya bölünebilir. 64 değer için 6, yani en fazla 7 karşılaştırma.

orta (mid)
bulundu
elendi
hedef

0 / 14 adım

Aramanın seçebileceği her orta; bir çalıştırma aşağı giden tek bir yoldur. Seviye: 5 = ⌈log₂(24 + 1)⌉, gerekebilecek en fazla karşılaştırma.

Hız 8 adım / sn

Boşluk: oynat veya duraklat. Sol ve sağ oklar: adım adım. Home ve End: atla.

Şunu deneyin: Dizide olmayan bir hedef seçin. Arama yine de en fazla ⌈log₂(n + 1)⌉ karşılaştırmada, lo hi'yi geçtiğinde biter.

Nasıl çalışır

İkili arama, hedefin hâlâ bulunabileceği kısmın etrafında lo ve hi adlı iki işaret tutar. Ortadaki değere bakar: hedefse iş biter; küçükse hedef yalnızca sağda olabilir, lo ortanın ötesine geçer; büyükse hi ortanın önüne geçer. Her adım kalanı yarıya indirir: 64 değer en fazla 7, bir milyon en fazla 20 karşılaştırma ister. lo, hi'yi geçtiğinde hiçbir şey kalmaz: değer dizide yoktur.

Ne zaman iyi bir seçimdir

Veri sıralıysa ve herhangi bir konuma atlayabiliyorsanız ikili arama kullanın: sıralı listede bir kelime, sürüm geçmişinde bir sürüm, git bisect, sıralı diziye ekleme yeri. Sırasız veride yanlış cevap verir; önce sıralamak ancak çok kez arayacaksanız kârlıdır.