Arama algoritmaları, bilgisayar bilimlerinin temel taşlarından birini oluşturur ve geniş bir uygulama yelpazesi bulunmaktadır. Veri işleme, veri tabanları, bilgisayar grafikleri ve daha birçok alanda, verileri düzenlemek ve hedeflenen bilgilere erişmek için arama algoritmalarına ihtiyaç duyulur. Bu makalede, geleneksel arama algoritmalarından farklı bir yaklaşım olan Fibonacci Search tekniği üzerinde bir inceleme yapacağız.

Fibonacci Search Nedir?

Fibonacci Search, sıralanmış bir dizi içinde bir öğenin konumunu belirlemek için Fibonacci sayılarını kullanır. Bu algoritma, veri koleksiyonunun belirli bir bölümünü ele alır ve bu bölümü alt dizilere bölerken Fibonacci sayılarına dayalı bir indeks hesaplaması yapar. Bu yaklaşım, veri koleksiyonu içindeki hedef öğeyi hızlı bir şekilde bulmak için kararlı ve etkili bir yol sunar.

Fibonacci Sayıları Nedir?

Fibonacci sayıları, her sayının kendisinden önceki iki sayının toplamı olduğu bir sayı dizisidir. Bu sayı dizisi şu şekildedir: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … Fibonacci sayılarının özelliği, sayılar büyüdükçe birbirleriyle oranlarının yaklaşık olarak 1.61803 (altın oran) olduğudur.

Fibonacci Search Algoritması

Fibonacci Search algoritması aşağıdaki adımları izler:

1. Başlangıçta iki Fibonacci sayısı olan F(k-2) ve F(k-1) seçilir, böylece F(k-1) koleksiyonun boyutundan küçük ve F(k-2) koleksiyonun boyutundan büyük olur.
2. Şu andaki aralık arr[0..F(k)] içinde bir öğeyi aramak için k değeri hesaplanır.

3. arr[F(k-2)] ve arr[F(k-1)] arasında bir karşılaştırma yapılır.

   • Eğer aranan öğe, arr[F(k-2)]‘den küçükse, arama aralığı arr[0..F(k-2)] olarak güncellenir ve işlem tekrarlanır.
   • Eğer aranan öğe, arr[F(k-2)]‘den büyükse, arama aralığı arr[F(k-2)..F(k-1)] olarak güncellenir ve işlem tekrarlanır.
   • Eğer aranan öğe, arr[F(k-2)] ile arr[F(k-1)] arasındaki öğeye eşitse, öğe bulunmuş olur.
4. Aranan öğe bulunana kadar veya arama aralığı boşalana kadar bu adımlar tekrarlanır.

Aşağıda, Fibonacci Search algoritmasının basit bir pseudocode örneği verilmiştir:

function FibonacciSearch(arr, x):
    n = length(arr)
    fibM = 0    // Fib(k-2)
    fibN = 1    // Fib(k-1)
    fibK = fibM + fibN

    while (fibK < n):
        fibM = fibN
        fibN = fibK
        fibK = fibM + fibN

    offset = -1

    while (fibK > 1):
        i = min(offset + fibM, n - 1)

        if (arr[i] < x):
            fibK = fibN
            fibN = fibM
            fibM = fibK - fibN
            offset = i

        else if (arr[i] > x):
            fibK = fibM
            fibN = fibN - fibM
            fibM = fibK - fibN

        else:
            return i  // Element found at index i

    if (fibN == 1 && arr[offset + 1] == x):
        return offset + 1  // Element found at index offset + 1

    return -1  // Element not found

Zaman ve Alan Karmaşıklığı

Fibonacci Search, ortalama durumda O(log n) zaman karmaşıklığına sahiptir. En kötü durumda da O(n) kadar iyi performans gösterir. Alan karmaşıklığı ise O(1) olarak kabul edilir.

Kullanım Alanları

Fibonacci Search, özellikle büyük sıralanmış koleksiyonlarda ve özellikle altın oranın belirli bir rol oynadığı alanlarda kullanılır. İdeal olarak, aranacak öğenin yerini yaklaşık olarak tahmin etmek ve bu nedenle aramayı optimize etmek istediğiniz durumlar için uygundur.

Fibonacci Search, geleneksel arama algoritmalarından farklı bir yaklaşım sunar ve sıralanmış veri koleksiyonlarında hızlı arama yapmak için kullanışlıdır. Fibonacci sayılarının özelliği, bu algoritmanın verimliliğini artırır. Ancak, veri koleksiyonlarının boyutu ve yapısı gibi faktörler algoritmanın performansını etkileyebilir, bu nedenle kullanmadan önce dikkatlice düşünülmesi gereken bir yöntemdir.

GoLang’de Fibonacci Search uygulaması:

package main

import (
	"fmt"
)

func FibonacciSearch(arr []int, x int) int {
	n := len(arr)
	fibM, fibN, fibK := 0, 1, 0

	for fibK < n {
		fibM, fibN = fibN, fibK
		fibK = fibM + fibN
	}

	offset := -1

	for fibK > 1 {
		i := min(offset+fibM, n-1)

		if arr[i] < x {
			fibK = fibN
			fibN = fibM
			fibM = fibK - fibN
			offset = i
		} else if arr[i] > x {
			fibK = fibM
			fibN = fibN - fibM
			fibM = fibK - fibN
		} else {
			return i
		}
	}

	if fibN == 1 && arr[offset+1] == x {
		return offset + 1
	}

	return -1
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	arr := []int{10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100}
	x := 85

	index := FibonacciSearch(arr, x)
	if index != -1 {
		fmt.Printf("%d found at index %d.\n", x, index)
	} else {
		fmt.Printf("%d not found.\n", x)
	}
}

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

85 found at index 8.

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

Kaynaklar

• https://en.wikipedia.org/wiki/Fibonacci_search_technique