İkili Arama
- İngilizcesi
- Binary Search
- Okunuşu
- baynıri sörç
Günlük kullanımda iki ad da yaygın.
Kısaca
İkili arama, sıralı bir listedeki bir değeri arama aralığını sürekli yarıya bölerek bulan bir algoritmadır; her öğeyi denetlemek yerine O(log n) sürer.
İkili arama (binary search) nedir?
İkili arama, sıralı bir koleksiyonda hedef bir değeri arar. Hedefi ortadaki öğeyle karşılaştırır: eşleşirlerse arama biter; hedef daha küçükse sol yarıda, daha büyükse sağ yarıda devam eder. Her adım kalan öğelerin yarısını eler.
Aralık her seferinde yarıya indiği için ikili arama en fazla yaklaşık log2(n) adım gerektirir; bu O(log n) süredir. Bir milyon öğelik sıralı bir liste için bu en fazla 20 karşılaştırma, bir milyar öğe için yaklaşık 30'dur; öğelere tek tek bakan doğrusal aramada ise bir milyara kadar denetim gerekebilir. Döngü tabanlı sürüm ayrıca yalnızca O(1) ek bellek gerektirir.
Diğer oyuncunun yalnızca daha yüksek ya da daha düşük dediği sayı tahmin oyunu gibi çalışır: en akıllı strateji her zaman kalan aralığın ortasını tahmin etmektir. İkili arama; sıralı dizilerde öğe aramada, veritabanı indekslerinde ve arama ağaçlarında, Python'ın bisect modülü gibi standart kütüphane araçlarında ve commit geçmişini tekrar tekrar yarıya bölerek hatayı getiren commit'i bulan git bisect içinde kullanılır.
İkili arama yalnızca dizi gibi indeksle hızlı erişim sağlayan sıralı verilerde çalışır; bağlı listede yalnızca ortadaki öğeye ulaşmak bile O(n) sürer. Ayrıca sinsi biçimde yanlış yapmak kolaydır: döngü sınırlarında bir eksik ya da fazla hataları yaygındır ve sabit boyutlu tamsayılı dillerde ortayı (low + high) / 2 olarak hesaplamak taşmaya yol açabilir; bu yüzden low + (high - low) / 2 daha güvenli biçimdir. Bir algoritma olan ikili aramayı, değerleri aynı şekilde aranabilecek biçimde saklayan bir veri yapısı olan ikili arama ağacıyla karıştırmayın.
Bir bakışta
Önemli noktalar
- İkili arama, verinin sıralı olmasını gerektirir.
- Doğrusal aramadaki O(n)'e karşılık O(log n) sürede çalışır.
- Her karşılaştırma kalan öğelerin yarısını eler.
- İndeksle hızlı erişim gerektirir; bu yüzden bağlı listelere değil dizilere uygundur.
- Döngü sınırlarındaki bir eksik ya da fazla hataları en yaygın hatadır.
Örnek
def binary_search(items, target):
# items must be sorted in ascending order
low, high = 0, len(items) - 1
while low <= high:
mid = (low + high) // 2
if items[mid] == target:
return mid # found it
if items[mid] < target:
low = mid + 1 # target is in the right half
else:
high = mid - 1 # target is in the left half
return -1 # target is not in the list
print(binary_search([2, 5, 8, 12, 16, 23, 38], 23)) # 5Sık sorulan sorular
İkili arama için liste neden sıralı olmalı?
İkili arama, hedefi ortadaki öğeyle karşılaştırarak hangi yarıyı eleyeceğine karar verir. Bu karar yalnızca soldaki her şey daha küçük, sağdaki her şey daha büyükse doğrudur; bu da yalnızca sıralı veri için geçerlidir.
İkili aramanın zaman karmaşıklığı nedir?
İkili arama en kötü ve ortalama durumda O(log n), ortadaki öğenin hedef olduğu en iyi durumda ise O(1) sürede çalışır. Döngü tabanlı sürüm O(1) ek bellek kullanırken özyinelemeli sürüm çağrı yığını için O(log n) kullanır.
Sırf ikili arama yapmak için veriyi sıralamaya değer mi?
Sıralamanın maliyeti O(n log n)'dir; bu yüzden yalnızca aynı veriyi birçok kez arıyorsanız karşılığını verir. Tek bir arama için O(n) doğrusal arama daha hızlıdır; çok sayıda tam anahtarlı arama içinse çoğu zaman bir hash tablosu daha da iyidir.
İlgili sayfalar
- AlgoritmaProgramlamanın Temelleri, s. 1Algoritma, bir listeyi sıralamak ya da en kısa yolu bulmak gibi bir sorunu çözmek veya bir işi tamamlamak için izlenen, sonlu ve adım adım yönergeler bütünüdür.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- Sıralama AlgoritmasıVeri Yapıları, s. 30Sıralama algoritması, öğeleri sayıları küçükten büyüğe ya da adları alfabetik olarak sıralamak gibi tanımlı bir düzene sokan adım adım bir yöntemdir.
- DiziProgramlamanın Temelleri, s. 15Dizi, tek bir ad altında saklanan ve her öğesine genellikle 0'dan başlayan indeks adlı sayısal konumuyla erişilen, sıralı bir değerler koleksiyonudur.
- AğaçVeri Yapıları, s. 2Ağaç, kenarlarla bağlı düğümlerden oluşan hiyerarşik bir veri yapısıdır; en üstte tek bir kök düğüm ve altında dallanan çocuk düğümler bulunur.
- Veritabanı İndeksiVeritabanları, s. 38Veritabanı indeksi, tüm tabloyu taramadan satırları hızla bulmayı sağlayan, bir kitabın sonundaki dizine benzeyen bir veri yapısıdır.
- Doğrusal AramaVeri Yapıları, s. 14Doğrusal arama (linear search), bir değeri listenin öğelerini baştan tek tek kontrol ederek eşleşme bulana ya da sona ulaşana kadar arar ve O(n) zaman alır.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin