Search algorithms form one of the cornerstones of computer science and have a wide range of applications. In data processing, databases, computer graphics, and many other fields, search algorithms are needed to organize data and access targeted information. In this article, we will examine the Fibonacci Search technique, which is a different approach from traditional search algorithms.

What is Fibonacci Search?

Fibonacci Search uses Fibonacci numbers to determine the position of an element within a sorted array. This algorithm takes a specific part of the data collection and calculates an index based on Fibonacci numbers while dividing this part into subsequences. This approach provides a stable and effective way to quickly find the target item within the data collection.

What are Fibonacci Numbers?

Fibonacci numbers are a sequence of numbers where each number is the sum of the two numbers before it. This number sequence is as follows: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, … The feature of Fibonacci numbers is that as the numbers grow, their ratio to each other is approximately 1.61803 (golden ratio).

Fibonacci Search Algorithm

The Fibonacci Search algorithm follows the following steps:

1. Initially, two Fibonacci numbers F(k-2) and F(k-1) are selected so that F(k-1) is less than the size of the collection and F(k-2) is larger than the size of the collection It is possible.
2. To search for an element in the current range arr[0..F(k)], the value k is calculated.

3. A comparison is made between arr[F(k-2)] and arr[F(k-1)].

   • If the searched item is less than arr[F(k-2)], the search range is updated to arr[0..F(k-2)] and the process is repeated.
   • If the searched item is greater than arr[F(k-2)], the search range is updated to arr[F(k-2)..F(k-1)] and the process is repeated.
   • If the searched item is equal to the item between arr[F(k-2)] and arr[F(k-1)], the item is found.
4. These steps are repeated until the searched item is found or the search range is empty.

Below is a simple pseudocode example of the Fibonacci Search algorithm:

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

Time and Space Complexity

Fibonacci Search has O(log n) time complexity in the average case. In the worst case, it performs as well as O(n). The field complexity is considered to be O(1).

Usage areas

Fibonacci Search is mainly used in large ordered collections and especially in areas where the golden ratio plays a certain role. Ideally, it is suitable for situations where you want to approximate the location of the item to be searched and therefore optimize the search.

Fibonacci Search offers a different approach than traditional search algorithms and is useful for quickly searching through sorted collections of data. The property of Fibonacci numbers increases the efficiency of this algorithm. However, factors such as the size and structure of data collections can affect the performance of the algorithm, so it is a method that should be carefully considered before using it.

Fibonacci Search implementation in GoLang:

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)
	}
}

When the program is run, its output will be as follows.

85 found at index 8.

The working version of the program can be accessed from here.

Resources

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