Interpolation Search algoritması Binary Search algoritmasının modifiye edilmiş halidir diyebiliriz. Binary Search’te algoritma, arama yapılan listenin ortasına gider.(n/2) Interpolation Search’te ise Binary Search’te her adımda gidilen ortanca index, bir formül yardımıyla belirlenir. Bu işlemle daha az adımda aranan değeri bulmak hedeflenir.
Ortanca değeri hesaplamak için şu formül kullanılmaktadır;
orta = sol + ((x – a[sol]) * ( sag – sol) ) / ( a[sag] – a[sol])
sol : dizinin sol taraf indis değeri
sağ : dizinin sağ taraf indis değeri
a[sol] : sol indisli değer
a[sağ] : sağ indisli değer
x : aranan değer
Burada dikkat edilmesi gereken nokta arama yapılacak dizi elemanlarının dağılımı y=a*x+b şeklinde ne kadar lineer bir dağılım gösterir ise bu algoritmanın o kadar hızlı sonuç vereceğidir.
Aşağıda ki python kodlarını inceleyip denemeler yaparsanız a[i]=2*i+7 şeklinde dizinin elemanları oluşturulduğu için sonucun ne kadar hızlı bulunduğunu göreceksiniz. Oysa a[i]=2*i*i+7*i+5 şeklinde dizinin elemanları oluşturulsa idi sonuç çok daha zaman alacaktı. Binary Search daha hızlı yanıt bile verebilir bu durumda. Binary ve interpolation search algoritmalarını karşılaştıran şu yazımı okumanızda fayda var.
# ikili arama algoritması
print("Dizinin eleman sayısını giriniz.")
n = int(input())
a = [0] * (n)
for i in range(0, n - 1 + 1, 1):
a[i] = 2 * i + 7
print("Dizinin içinde aramak istediğniz bir değer giriniz.")
x = int(input())
sayac = 0
ilk = 0
son = n - 1
if x < a[ilk]:
print("Aranan değer dizide bulunmamaktadır.")
else:
o = ilk + int(((x - a[ilk]) * (son - ilk)) / (a[son] - a[ilk]))
while x != a[o] and son - o > 1:
if x < a[o]:
son = o
o = ilk + int(((x - a[ilk]) * (son - ilk)) / (a[son] - a[ilk]))
else:
ilk = o
o = ilk + int(((x - a[ilk]) * (son - ilk)) / (a[son] - a[ilk]))
sayac = sayac + 1
if x == a[ilk]:
print("Aranan " + str(x) + " değeri dizinin içindedir, " + str(ilk) + " indis değerli sayıya eşittir." + " " + str(sayac) + " kere arama yapıldı")
else:
if x == a[son]:
print("Aranan " + str(x) + " değeri dizinin içindedir, " + str(son) + " indis değerli sayıya eşittir." + " " + str(sayac) + " kere arama yapıldı")
else:
if x == a[o]:
print("Aranan " + str(x) + " değeri dizinin içindedir, " + str(o) + " indis değerli sayıya eşittir." + " " + str(sayac) + " kere arama yapıldı")
else:
print("Aranan değer dizide bulunmamaktadır.")
Flowgorithm uygulaması ile yaptığım flowcharta buradan bakabilirsiniz.
Ayrıca programın tamamını da buradan indirebilirsiniz.
Not: Kodda önemli bir hatayı bulup düzeltme yaptığı için Marziye hanıma teşekkür ederim.