İkili Arama Nedir?

İkili arama nedir?

İkili arama, sıralı bir listede bir değeri bulmanın en hızlı yollarından biridir. Listenin baştan sona taranması yerine her adımda ortadaki elemana bakılır. Aranan değer daha küçükse sol yarıya, daha büyükse sağ yarıya geçilir. Böylece her adımda kalan liste ikiye bölünür.

Nasıl çalışır?

Günlük hayattan bir örnek: Kalın bir sözlükte "kalem" kelimesini ararken ilk sayfadan başlamazsınız. Sözlüğü ortadan açarsınız ve "m" harfine denk geldiyseniz önceki yarıya dönersiniz. Her denemede aranacak sayfa sayısı yarıya iner.

Yazılımda bu şöyle işler. 1'den 100'e kadar sıralı sayılar içinde 73'ü arayalım. Ortadaki 50'ye bakılır; 73 daha büyük olduğu için 51-100 aralığına geçilir. Yeni orta nokta 75'tir; 73 daha küçük olduğu için 51-74 aralığı kalır. Birkaç adım daha sonra değer bulunur. Bu iş toplamda en fazla 7 adım sürer.

Doğrusal aramadan farkı

Doğrusal arama listeyi tek tek gezer. Bir milyon elemanlı bir listede en kötü durumda bir milyon karşılaştırma yapar. İkili arama aynı listede en fazla 20 civarında karşılaştırmayla sonuca ulaşır. Bu farkın teknik adı O(n) ile O(log n) arasındaki farktır.

Nelere dikkat etmeli?

İlk şart listenin sıralı olmasıdır. Sırasız bir listede ikili arama yanlış sonuç verir. Kendi kodunuzu yazarken orta noktayı hesaplarken sınır hatalarına dikkat edin; aralığın bir eksik ya da bir fazla alınması, en sık yapılan hatadır. Çoğu dilde hazır fonksiyonlar bulunur: Python'daki bisect modülü bunlardan biridir.