Bilmek istediğin her şeye ulaş

İkili arama (Binary Search) algoritması nasıl yazılır?

Mantık şu; 

Elimizde 100 satırlık bir dizi olsun.
İçinde farklı aralıklarla ve sürekli artan sayılar bulunsun.

Atıyorum 64ü aratmak istiyoruz.

Diziyi tam göbekten ikiye bölüyoruz ve ilk 49. satıra bakıyoruz (malum diziler 0. elemandan başlar). İçindeki veri 64 mü? Hayır! 76.

Şimdi. Dizimiz sürekli artan bir dizi olduğuna göre 49. satırdan 99a kadar giden satırların 76 sayısından, doğal olarak da 64den büyük olduğu kesin. O zaman 49-99 arasındaki satırlarla işimiz bitti.

Hedef 0 - 49.

Bundan sonra da yine bu 50 satırlık diziyi ikiye bölüyoruz ve tam ortadaki sayıya eşit mi diye bakıyoruz. Yoksa sayıdan büyük mü küçük mü diye bakınıp ona göre 2ye bölüyoruz diziyi.
  • Paylaş
Bilgisayar Bilimindeki karşılığı olarak soruyorsanız yukarıdaki Aleks'in açıklaması yeterli olacaktır.

Search engine yapısında soruyorsanız;

Öncelikle binary files definition list'in olmalı. Bu list'e göre media type'ları tanımlaman gerek. Tabii bu type'ların bit dizilimlerini file formatlarını araştırarak öğrenebilirsin. Örneğin; Müzik dosyalarının ilk 3 byte'ında dosya uzantısı. Son 250 byte'ın da hangi sanatçı olduğu, şarkı adı gibi bilgiler vardır. (Tam olarak değerler bunlar olmayabilir farklı bit aralıklarında da bu bilgiler olabilir sadece örnek için yazdım.)

Bu tanımlamaları yaptıktan sonra gelen dosyanın PDF'mi MP4'mü olduğunu ayırabilirsin. Bu ayrımı yaptıktan sonra file content kısmında binary olarak arama yapabilirsin. Bu da demek oluyor ki elindeki String'i de binary format'a dönüştürüp, file content ile match ettirmen gerek. Tabii dosya boyutları büyüdükçe her bit blok'u için bunu yapman zor olur. Arayacağın binary'nin size'ı kadar file content'i block'lara bölmen gerek. HEADER ve FOOTER bilgilerini filtreledikten sonra kalan content kısmını eşit parçalara ayırıp bir RDBMS üzerinde HASH'ler ifade ederek, sonraki aramalarını direkt DB üzerinden çok daha hızlı yapabilirsin.

Tam olarak ne için binary search algoritması yazmak istediğini belirtirsen daha iyi yardımcı olabilir. Yaklaşık 4 yıldır search algoritmaları ve search engine kernel development üzerine R&D yaptığımdan, sanırım Türkiye'de bulabileceğin en iyi kaynak buarada :)
  • Paylaş
Sonraki Soru
HESAP OLUŞTUR

İstatistikler

1364 Görüntülenme7 Takipçi3 Yanıt