Interpolation Arama, sıralı bir dizide hızlı bir şekilde arama yapmak için kullanılan bir arama algoritmasıdır. Bu algoritma, binary search gibi sıralı dizilerde çalışırken, aranan değeri bulmak için tahmini bir konum belirlemeye dayanır.

İki temel koşula dayalıdır:

1. Dizi sıralı olmalıdır.
2. Dizideki elemanlar arasındaki farklar tahmin edilebilir ve düzensiz olmamalıdır.

Interpolation Search Nasıl Çalışır?

Interpolation search algoritması, aranan değerin tahmini konumunu hesaplamak için bir formül kullanır. Bu formül genellikle aşağıdaki gibidir:

position = low + ((value - arr[low]) / (arr[high] - arr[low])) * (high - low)

Burada:

• arr[] => öğelerin aranması gereken dizi.
• low => başlangıç dizini indeksini temsil eder.
• high => bitiş dizini indeksini temsil eder.
• value => aranan değeri temsil eder.

Algoritma şu adımları izler:

1. Başlangıçta low ve high değerleri, dizinin başlangıç ve bitiş indekslerini temsil eder.
2. Tahmini konumu hesaplamak için yukarıdaki formül kullanılır.
3. Eğer tahmini değer aranan değere eşitse, arama başarılıdır ve tahmini konum döndürülür.
4. Eğer tahmini değer aranan değerden küçükse, arama sağ tarafta devam eder, yani low değeri güncellenir.
5. Eğer tahmini değer aranan değerden büyükse, arama sol tarafta devam eder, yani high değeri güncellenir.
6. Bu işlem, aranan değer bulunana veya low değeri high değerinden büyük olana kadar devam eder.

Diğer Bazı Arama Algoritmalarıyla Karşılaştırma

• Linear Search: Linear search algoritması, sıralı olmayan veya sıralı olsa bile sıralı olduğu bilgisi kullanılmayan dizilerde kullanılır. Her elemanı sırayla kontrol eder. Interpolation search, daha hızlı bir alternatif sunar çünkü tahmini konumu kullanarak elemanları hızla yaklaştırabilir. Karmaşıklığı O(n)‘dir.
• Binary Search: Binary search, her adımda dizinin ortasındaki elemanı kontrol eder. Interpolation search, elemanlar arasındaki tahmini farkları kullanarak daha hızlı bir tahmin yapar. Ancak düzensiz aralıklara sahip dizilerde performansı düşebilir. Karmaşıklığı O(log n)‘dir.
• Jump Search: Jump search, bir aralığı atlama adımlarıyla tarar. Jump search’ün adımları sabitken, interpolation search adımları tahmini konumun farkına göre değişir. Karmaşıklığı O(√ n)‘dir.

Interpolation search, dizinin düzgün bir şekilde dağıldığı durumlarda binary search’ten daha hızlı olabilir. Ancak dizi elemanları arasındaki farklar büyük ve düzensizse, algoritma doğru tahminler yapamayabilir ve hatta binary search’ten daha yavaş olabilir.

Karmaşıklık

• Time: O(log(log(n))

GoLang’de Interpolation Search Algoritması uygulaması:

package main

import (
	"fmt"
)

func interpolationSearch(arr []int, target int) int {
	low := 0
	high := len(arr) - 1

	for low <= high && target >= arr[low] && target <= arr[high] {
		if low == high {
			if arr[low] == target {
				return low
			}
			return -1
		}

		pos := low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low])

		if arr[pos] == target {
			return pos
		}

		if arr[pos] < target {
			low = pos + 1
		} else {
			high = pos - 1
		}
	}

	return -1
}

func main() {
	arr := []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}
	target := 11

	index := interpolationSearch(arr, target)
	if index != -1 {
		fmt.Printf("Aranan değer %d indeksinde bulundu.\n", index)
	} else {
		fmt.Println("Aranan değer bulunamadı.")
	}
}

Bu örnek, verilen bir sıralı dizi üzerinde Interpolation Search algoritmasını uygular. interpolationSearch fonksiyonu, dizi ve hedef değeri alır ve hedef değerin dizideki indeksini döndürür. Eğer hedef değer bulunamazsa -1 döner. Bu örnekte, aranan değer 11 ve verilen dizi [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] şeklindedir.

Program çalıştırıldığında çıktısı aşağıdaki gibi olacaktır.

Aranan değer 5 indeksinde bulundu.

Programın çalışır haline şuradan erişilebilir.

Kaynaklar

• https://en.wikipedia.org/wiki/Interpolation_search
• https://www.techiedelight.com/interpolation-search/
• https://www.topcoder.com/thrive/articles/interpolation-search