Alfabetik bir sıralı listede binary search'den daha performanslı algoritma?
interpolation search var ama implementasyonu kompleks bir algoritma, kazanacağın performansa değer mi bilmem ben olsam binary search ile devam ederdim.
bu elindeki verinin buyuklugune ve elindeki veride birbirinin ayni olan verinin miktarina bagli olarak degisir. eger elindeki veri ve tekrar eden veri az ise, ayni zamanda memory verimliligi senin icin onemli degil ise hash table O(1) verimlilikle calisirken binary search O(log n) verimlillikle calisir.
Ama eger elindeki veri adedi sonsuza yaklasir ise ve tekrar eden veri cok ise binary search mantikli hale gelmeye baslar. Binary search de icinde cesitli varyasyonlar barindirir. Normalde binary search de hic kafa yormadan elindeki veriyi ikiye bolup islem yaparsin. ama elindeki veri icinde biraz kafa yorarak ortadan ikiye bolmek yerine biraz mantikli yerden bolerek hizini arttirabilirsin.
ornegin turkce kitap halindeki sozlukte bir kelimeyi ararken mantik olarak binary search yapariz. sozlugun sayfalarini ortadan ikiye boleriz ve aradigimiz kelime alfabetik olarak sagda mi solda mi diye bakar ona gore yine ikiye boleriz. ama biraz daha fazla proses yaparsak ve aradigimiz kelime z harfi ile baslar ise ortadan ikiye bolmek yerine sozlugun sonlarina yakin bir yerden boleriz. bu sayede daha az bolme ile aradigimizi bulma sansini arttiririz. amac elimizdeki verinin niteligine gore en dogru tahmini yapmak.
elbette veriyi sirali olmasinin disinda belli bir mantik cercevesinde haritalandirabilir isek, ornegin google tarafindan kullanilan rank algorithm ve graph gibi daha hizli sonuc alabiliriz.
ama sonucta hersey @nahtoderfahrung da bahsettigi gibi kazanacagin performansa degmesi olayi, ve elindeki veri sonsuza yaklastikca ve anlamsiz ise tahminime gore en verimli arama algoritmasi binary search olacaktir. bu biraz bilgisayar biliminden daha cok matematikcilerin ispatlayacagi bir cozum, umarim bir matematici daha iyi bir aciklama getirebilir.