Ara Değer Araması (Interpolation Search)

Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde sıralı bir veri kümesi üzerinde arama yapmak için kullanılan yöntemlerden birisidir. Buna göre arama sırasında aşağıdaki formül kullanılarak orta nokta bulunur:

orta = sol + ((x-a[sol]) * (sag – sol) ) / ( a[sag] – a[sol])

Yukarıdaki sol ve sag ile ifade edilen değerler arama yapılan alandaki aralığın başlangış ve bitiş indisleridir. a dizisi ise arama yapılan dizinin ismidir. x değeri ise aranan değer olarak kabul edilir.  Buna göre aşağıdaki sayısal örnek üzerinden arama algoritmasının çalışmasını inceleyelim:

a dizisi : 1 3 4 5 6 8 9 11 12

indisler: 0 1 2 3 4 5 6 7    8

Yukarıdaki a dizisindeki elemanlardan örneğin 6 sayılı değeri aradğımızı düşünelim. Arama işlemimiz dizinin tamamında yapılacağına göre sol : 0 ve sag : 8 olarak aramaya başlıyoruz. Öncelikle orta değeri yukarıda verilen formül ile bulalım:

sol = 0 // arama alanının başlangıcı

sag = 8 // arama alanının sonu

a[sol] = 1 // dizideki sag değeri

a[sag] = 12 //dizideki sol değeri

x = 6 // aranan değer

orta = 0 + (( 6- 1) * (8 – 1)) / (12-1)

orta = 35 /11  ~ 3 olarak bulunur. (sonuç yuvarlanır)

dolayısıyla a[3] değeri ara değerimiz olmaktadır ve bu değerin aradığımız değer olup olmadığı kontrol edilir. Buna göre a[3] = 5’tir ve aradğımız değerden küçüktür.

Şayet bulunan orta değeri aranan değerden küçükse aradığımız değer daha sağda olduğu için orta değer, sol olarak kabul edilip işlem tekrarlanır.

Şayet bulunan orta değeri aranan değerden büyükse aradığımız değer daha solda olduğu için orta değer, sağ olarak kabul eidlip işlem tekrarlanır.

Buna göre orta değer yeni sol değerimiz olacak ve formül tekrarlanacaktır:

sol = 3 // arama alanının başlangıcı

sag = 8 // arama alanının sonu

a[sol] = 5 // dizideki sag değeri

a[sag] = 12 //dizideki sol değeri

x = 6 // aranan değer

orta = 3 + (( 6- 5) * (8 – 3)) / (12-5)

orta = 3 + 5 /7  ~ 4 olarak bulunur. (sonuç yuvarlanır)

Sonuçta a[4]=6 değeri bulunmuştur ve işlem biter.