İ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)
- Θ(log n)
- en kötü O(log n)
- bellek O(1)
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.
Bu sayfadaki diğer terimler
- 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.
- orta (mid)
- bulundu
- elendi
- hedef
Ş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.