İkili arama algoritması, sıralı bir veri dizisinde aranan değerin bulunabileceği aralığı her karşılaştırmada yaklaşık yarıya indirerek çalışan arama yöntemidir. Önce aralığın ortasındaki öğe değerlendirilir. Aranan değerle yapılan karşılaştırmaya göre alt ya da üst yarıda aramaya devam edilir. Değer bulunduğunda veya aranacak aralık boşaldığında işlem sona erer.[1]
SIRALAMA KOŞULU
Yöntemin temel koşulu, verilerin karşılaştırmada kullanılan ölçüte göre önceden sıralanmış olmasıdır. Ortadaki öğeden küçük bir değer aranıyorsa büyük öğelerin bulunduğu yarı elenir; daha büyük değer için ters yöndeki yarı elenir. Bu çıkarım sıralamaya dayanır. Sırasız bir dizide aynı eleme işlemi doğru sonucu garanti etmez; bu nedenle arama ile sıralama ayrı işlemler olarak düşünülür.[1]
İŞLEM SAYISI
Ortadaki öğeye doğrudan erişilebilen bir dizide ikili aramanın zaman karmaşıklığı O(log n) düzeyindedir. Burada n, öğe sayısını gösterir. Her adım aralığı küçülttüğü için veri sayısı büyüdükçe gereken karşılaştırmalar yavaş artar. Ancak bağlı listede ortadaki öğeye ulaşmak için bağlantıları izlemek gerekir; karşılaştırma sayısı logaritmik kalsa da toplam dolaşma maliyeti doğrusal olabilir.[1]
EKLEME NOKTASI VE YİNELENEN DEĞERLER
İkili aramanın türevleri, bir değerin yerini aramanın yanında sıralamayı koruyacak ekleme noktasını da bulabilir. Python'un bisect araçları, eşit değerlerin öncesindeki veya sonrasındaki sınırı belirleyebilir. Ekleme noktasını bulmakla öğeyi gerçekten diziye yerleştirmek farklı maliyetler taşır: arama logaritmik olsa bile elemanların kaydırılması nedeniyle ekleme doğrusal zaman alabilir.[2]