Fibonacci Search In Data Structures | Working & More (+Examples)

0 min read

In the world of data structures and algorithms, efficient searching is the cornerstone of performance. While Binary Search often takes the spotlight for sorted arrays, there's another lesser-known yet powerful technique—Fibonacci Search. Inspired by the mathematical Fibonacci sequence, this algorithm offers a unique approach to divide and conquer, often outperforming binary search in systems where the cost of accessing memory locations is not uniform.

In this article, we’ll explore what Fibonacci Search is, how it works, and why it can be a better alternative in specific scenarios. We’ll also dive into its implementation, analyze its time complexity, and compare it with traditional search techniques like binary and linear search.

What Is Fibonacci Search?

Fibonacci Search in data structures is a comparison-based search algorithm that operates on sorted arrays, utilizing the Fibonacci sequence to divide the array and efficiently narrow down the search space. Similar to Binary Search, it follows a divide-and-conquer approach, but instead of splitting the array into equal halves, it partitions the array using Fibonacci numbers. This strategy helps in reducing the number of comparisons and improving performance in certain memory access scenarios.

In simple terms, the Fibonacci Search checks for the desired element in a way that reflects the structure of Fibonacci numbers, minimizing the range of search at each step.

Origin Of The Name – The Fibonacci Sequence

The algorithm is named after the Fibonacci sequence, a famous mathematical series where each number is the sum of the two preceding ones. It starts like this:

 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

This sequence plays a central role in how the search positions are calculated. Instead of dividing the array strictly in half like Binary Search, Fibonacci Search uses Fibonacci numbers to calculate the index to compare, which often results in better locality of reference in systems with non-uniform memory access.

The use of Fibonacci numbers allows the algorithm to maintain a predictable and structured way to reduce the search interval, and this is particularly helpful when memory access time is variable, such as in tape storage or paged memory.

Where It Fits In The Family Of Search Algorithms

Fibonacci Search belongs to the family of divide-and-conquer search algorithms and is a variant of Binary Search. However, it introduces a unique twist:

Fibonacci Search is ideal when:

• You are working with sorted arrays.
• Your system has non-uniform access memory (e.g., tape drives, large databases).
• You want to minimize arithmetic operations (uses subtraction and bitwise shifts more than division).

Though Binary Search is generally faster in modern RAM-based systems, Fibonacci Search can be superior in legacy or specialized environments where cache behavior or memory latency matters more.

Fibonacci Search Algorithm

The Fibonacci Search algorithm uses Fibonacci numbers to calculate the index positions to inspect, rather than simply dividing the array in half as in Binary Search. It is designed for efficient search operations in sorted arrays, especially when memory access cost varies.

Here’s a detailed step-by-step explanation of how the algorithm works:

Step 1: Initialize Fibonacci Numbers

Find the smallest Fibonacci number (fibM) that is greater than or equal to the size of the array (n). Set two previous Fibonacci numbers:

• fibM_minus_1 = fibM - 1
• fibM_minus_2 = fibM - 2

These values help determine the offset while searching.

Step 2: Set Initial Offset

Initialize an offset = -1 to track the eliminated range from the front. This is crucial because we will eliminate parts of the array from the front as we go.

Step 3: Start the Search Loop

While fibM > 1, repeat the following steps:

1. Calculate index i = min(offset + fibM_minus_2, n - 1) (Use min to ensure the index stays within bounds.)
2. Compare the element at index i with the target:

If arr[i] < target:

→ Eliminate subarray from offset to i
→ Update Fibonacci numbers:
fibM = fibM_minus_1
fibM_minus_1 = fibM_minus_2
fibM_minus_2 = fibM - fibM_minus_1
offset = i

If arr[i] > target:

→ Eliminate subarray after i
→ Update Fibonacci numbers:
fibM = fibM_minus_2
fibM_minus_1 = fibM_minus_1 - fibM_minus_2
fibM_minus_2 = fibM - fibM_minus_1

If arr[i] == target:

→ Target found at index i. Return i.

Step 4: Final Comparison (Last Element)

• If fibM_minus_1 == 1 and arr[offset + 1] == target, return offset + 1.

Step 5: Element Not Found

• If the loop ends and no match is found, return -1.

Why It Works Efficiently:

• Reduces memory reads in systems with non-uniform access time.
• Uses subtraction (cheaper) instead of division.
• Skips over large chunks, similar to Binary Search but with better memory locality.

Pseudocode for Fibonacci Search

function fibonacciSearch(arr, target):
    n = length of arr

    # Initialize Fibonacci numbers
    fibM_minus_2 = 0         # (m-2)'th Fibonacci number
    fibM_minus_1 = 1         # (m-1)'th Fibonacci number
    fibM = fibM_minus_2 + fibM_minus_1  # m'th Fibonacci number

    # Find the smallest Fibonacci number >= n
    while fibM < n:
        fibM_minus_2 = fibM_minus_1
        fibM_minus_1 = fibM
        fibM = fibM_minus_2 + fibM_minus_1

    offset = -1

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

        if arr[i] < target:
            fibM = fibM_minus_1
            fibM_minus_1 = fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
            offset = i
        else if arr[i] > target:
            fibM = fibM_minus_2
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        else:
            return i  # Element found

    # Final comparison
    if fibM_minus_1 == 1 and offset + 1 < n and arr[offset + 1] == target:
        return offset + 1

    return -1  # Element not found

Code Implementation Of Fibonacci Search 

Let’s now look at a detailed code example to understand how Fibonacci Search works in data structures-

Code Example:

            #include 
#include 
using namespace std;

// Function to perform Fibonacci Search
int fibonacciSearch(const vector& arr, int target) {
    int n = arr.size();

    // Initialize the first two Fibonacci numbers
    int fibM_minus_2 = 0;     // (m-2)'th Fibonacci number
    int fibM_minus_1 = 1;     // (m-1)'th Fibonacci number
    int fibM = fibM_minus_1 + fibM_minus_2; // m'th Fibonacci number

    // Find the smallest Fibonacci number >= n
    while (fibM < n) {
        fibM_minus_2 = fibM_minus_1;
        fibM_minus_1 = fibM;
        fibM = fibM_minus_1 + fibM_minus_2;
    }

    // Marks the eliminated range from the front
    int offset = -1;

    // While there are elements to inspect
    while (fibM > 1) {
        // Check if fibM_minus_2 is a valid index
        int i = min(offset + fibM_minus_2, n - 1);

        // If target is greater, cut the subarray from offset to i
        if (arr[i] < target) {
            fibM = fibM_minus_1;
            fibM_minus_1 = fibM_minus_2;
            fibM_minus_2 = fibM - fibM_minus_1;
            offset = i;
        }
        // If target is smaller, cut the subarray after i+1
        else if (arr[i] > target) {
            fibM = fibM_minus_2;
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2;
            fibM_minus_2 = fibM - fibM_minus_1;
        }
        // Element found
        else {
            return i;
        }
    }

    // Compare the last element
    if (fibM_minus_1 && offset + 1 < n && arr[offset + 1] == target) {
        return offset + 1;
    }

    // Element not found
    return -1;
}

// Driver code
int main() {
    vector arr = {10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100};
    int target = 85;

    int index = fibonacciSearch(arr, target);

    if (index >= 0)
        cout << "Element found at index: " << index << endl;
    else
        cout << "Element not found in the array." << endl;

    return 0;
}

          

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy8gRnVuY3Rpb24gdG8gcGVyZm9ybSBGaWJvbmFjY2kgU2VhcmNoCmludCBmaWJvbmFjY2lTZWFyY2goY29uc3QgdmVjdG9yPGludD4mIGFyciwgaW50IHRhcmdldCkgewogICAgaW50IG4gPSBhcnIuc2l6ZSgpOwoKICAgIC8vIEluaXRpYWxpemUgdGhlIGZpcnN0IHR3byBGaWJvbmFjY2kgbnVtYmVycwogICAgaW50IGZpYk1fbWludXNfMiA9IDA7ICAgICAvLyAobS0yKSd0aCBGaWJvbmFjY2kgbnVtYmVyCiAgICBpbnQgZmliTV9taW51c18xID0gMTsgICAgIC8vIChtLTEpJ3RoIEZpYm9uYWNjaSBudW1iZXIKICAgIGludCBmaWJNID0gZmliTV9taW51c18xICsgZmliTV9taW51c18yOyAvLyBtJ3RoIEZpYm9uYWNjaSBudW1iZXIKCiAgICAvLyBGaW5kIHRoZSBzbWFsbGVzdCBGaWJvbmFjY2kgbnVtYmVyID49IG4KICAgIHdoaWxlIChmaWJNIDwgbikgewogICAgICAgIGZpYk1fbWludXNfMiA9IGZpYk1fbWludXNfMTsKICAgICAgICBmaWJNX21pbnVzXzEgPSBmaWJNOwogICAgICAgIGZpYk0gPSBmaWJNX21pbnVzXzEgKyBmaWJNX21pbnVzXzI7CiAgICB9CgogICAgLy8gTWFya3MgdGhlIGVsaW1pbmF0ZWQgcmFuZ2UgZnJvbSB0aGUgZnJvbnQKICAgIGludCBvZmZzZXQgPSAtMTsKCiAgICAvLyBXaGlsZSB0aGVyZSBhcmUgZWxlbWVudHMgdG8gaW5zcGVjdAogICAgd2hpbGUgKGZpYk0gPiAxKSB7CiAgICAgICAgLy8gQ2hlY2sgaWYgZmliTV9taW51c18yIGlzIGEgdmFsaWQgaW5kZXgKICAgICAgICBpbnQgaSA9IG1pbihvZmZzZXQgKyBmaWJNX21pbnVzXzIsIG4gLSAxKTsKCiAgICAgICAgLy8gSWYgdGFyZ2V0IGlzIGdyZWF0ZXIsIGN1dCB0aGUgc3ViYXJyYXkgZnJvbSBvZmZzZXQgdG8gaQogICAgICAgIGlmIChhcnJbaV0gPCB0YXJnZXQpIHsKICAgICAgICAgICAgZmliTSA9IGZpYk1fbWludXNfMTsKICAgICAgICAgICAgZmliTV9taW51c18xID0gZmliTV9taW51c18yOwogICAgICAgICAgICBmaWJNX21pbnVzXzIgPSBmaWJNIC0gZmliTV9taW51c18xOwogICAgICAgICAgICBvZmZzZXQgPSBpOwogICAgICAgIH0KICAgICAgICAvLyBJZiB0YXJnZXQgaXMgc21hbGxlciwgY3V0IHRoZSBzdWJhcnJheSBhZnRlciBpKzEKICAgICAgICBlbHNlIGlmIChhcnJbaV0gPiB0YXJnZXQpIHsKICAgICAgICAgICAgZmliTSA9IGZpYk1fbWludXNfMjsKICAgICAgICAgICAgZmliTV9taW51c18xID0gZmliTV9taW51c18xIC0gZmliTV9taW51c18yOwogICAgICAgICAgICBmaWJNX21pbnVzXzIgPSBmaWJNIC0gZmliTV9taW51c18xOwogICAgICAgIH0KICAgICAgICAvLyBFbGVtZW50IGZvdW5kCiAgICAgICAgZWxzZSB7CiAgICAgICAgICAgIHJldHVybiBpOwogICAgICAgIH0KICAgIH0KCiAgICAvLyBDb21wYXJlIHRoZSBsYXN0IGVsZW1lbnQKICAgIGlmIChmaWJNX21pbnVzXzEgJiYgb2Zmc2V0ICsgMSA8IG4gJiYgYXJyW29mZnNldCArIDFdID09IHRhcmdldCkgewogICAgICAgIHJldHVybiBvZmZzZXQgKyAxOwogICAgfQoKICAgIC8vIEVsZW1lbnQgbm90IGZvdW5kCiAgICByZXR1cm4gLTE7Cn0KCi8vIERyaXZlciBjb2RlCmludCBtYWluKCkgewogICAgdmVjdG9yPGludD4gYXJyID0gezEwLCAyMiwgMzUsIDQwLCA0NSwgNTAsIDgwLCA4MiwgODUsIDkwLCAxMDB9OwogICAgaW50IHRhcmdldCA9IDg1OwoKICAgIGludCBpbmRleCA9IGZpYm9uYWNjaVNlYXJjaChhcnIsIHRhcmdldCk7CgogICAgaWYgKGluZGV4ID49IDApCiAgICAgICAgY291dCA8PCAiRWxlbWVudCBmb3VuZCBhdCBpbmRleDogIiA8PCBpbmRleCA8PCBlbmRsOwogICAgZWxzZQogICAgICAgIGNvdXQgPDwgIkVsZW1lbnQgbm90IGZvdW5kIGluIHRoZSBhcnJheS4iIDw8IGVuZGw7CgogICAgcmV0dXJuIDA7Cn0K

Output: 

Element found at index: 8

Explanation:

In the above code example-

1. We start by including the necessary headers: <iostream> for input-output operations and <vector> to use the vector container from the Standard Template Library.
2. We define a function called fibonacciSearch that takes a sorted vector and the target value we want to find.
3. Inside the function, we first get the size of the array using arr.size().
4. We initialize the first three Fibonacci numbers: fibM_minus_2 = 0, fibM_minus_1 = 1, and fibM as their sum.
5. We enter a loop to find the smallest Fibonacci number greater than or equal to the size of the array. This helps define the range in which we will search.
6. We use an offset variable initialized to -1 to mark the eliminated portion from the start of the array.
7. Now, as long as fibM > 1, we keep checking subarrays for the target.
8. In each iteration, we calculate the index i as the minimum of offset + fibM_minus_2 and n - 1, so we stay within bounds.
9. If the element at index i is less than the target, we move our search window to the right and update the Fibonacci numbers accordingly. We also set the new offset to i.
10. If the element at index i is greater than the target, we reduce the search window to the left side and update the Fibonacci numbers again.
11. If the element at i is equal to the target, we return i because we've found the element.
12. After the loop, we check one last possible position: offset + 1, which might hold the target if it's the last remaining value.
13. If we find it there, we return the index. Otherwise, we return -1, indicating the target is not present.
14. In main(), we define a sample sorted array and a target value we want to search for.
15. We call fibonacciSearch with our array and target, and store the result in the variable index.
16. If the result is non-negative, we print the index where the target was found. Otherwise, we print that the element was not found.
17. Finally, we return 0 from main() to indicate that the program ended successfully.

Fibonacci Search vs Binary Search

Both Fibonacci Search and Binary Search are efficient algorithms used to search for elements in a sorted array, but they differ in their approach, underlying logic, and ideal use cases. Let’s compare them side-by-side to understand their strengths and limitations.

Time And Space Complexity Analysis Of Fibonacci Search

Understanding the efficiency of an algorithm is critical when deciding whether it's suitable for a given application. Let’s break down the time and space complexity of Fibonacci Search to see how it performs in different scenarios.

When To Use Fibonacci Search?

Below are the key situations and real-world applications where Fibonacci Search is a better choice:

1. Non-Uniform Memory Access (NUMA) Systems

In NUMA-based architectures, the time taken to access memory locations may vary depending on their proximity to a processor. Since Fibonacci Search tends to access memory more sequentially and avoids large jumps like Binary Search, it reduces latency and improves cache performance in such systems.

2. Tape Drives and Sequential Storage Media

Fibonacci Search is historically relevant in systems like magnetic tape drives or early sequential storage, where accessing a middle location is time-consuming. Here, the algorithm’s sequential-like access pattern minimizes unnecessary seeks, making it ideal for searching data on tape or other sequential-access media.

3. Hierarchical Memory Systems

In architectures where memory is accessed in hierarchical layers (like CPU cache, RAM, and disk), Fibonacci Search can be more efficient due to its favorable locality of reference. It often accesses closer memory locations, improving cache performance.

4. Embedded Systems with Limited Arithmetic Capabilities

In embedded systems where floating-point arithmetic or division operations are expensive or unsupported, Fibonacci Search is preferred. It avoids division and uses only addition and subtraction, which are computationally cheaper and faster on low-power devices.

5. Applications with High Read Costs

In applications where reading data from memory is expensive (such as remote sensing systems or networked databases), Fibonacci Search can help minimize the number of reads by narrowing the search space more predictably.

6. Index-Based Searching in Sorted Datasets

Some database systems or analytics engines use Fibonacci Search to optimize index lookups when the data is sorted but resides on storage mediums with varied access times (e.g., SSDs or HDDs).

7. Legacy Systems or Algorithms Requiring Predictable Access Patterns

In systems where predictable memory access patterns are crucial for performance or security reasons (such as real-time systems), Fibonacci Search may be used to maintain deterministic access behavior.

Conclusion

Fibonacci Search may not be as widely known as Binary Search, but it offers a valuable alternative in environments where memory access times are inconsistent or where sequential access patterns can significantly enhance performance. By leveraging the mathematical properties of the Fibonacci sequence, this algorithm allows efficient searching with minimal computational overhead, especially in systems that avoid division operations or favor locality of reference.

In today's landscape of diverse computing architectures—from NUMA systems to embedded devices and tape storage—understanding when and how to apply Fibonacci Search can lead to smarter, faster, and more resource-efficient software solutions.

Whether you're optimizing for hardware constraints or simply exploring alternative search strategies, Fibonacci Search remains a powerful tool in the arsenal of data structure and algorithm design.

Frequently Asked Questions

Q. What is the main advantage of Fibonacci Search over Binary Search?

The primary advantage of Fibonacci Search lies in its memory access pattern. While Binary Search divides the array in half and often jumps across memory locations, Fibonacci Search uses sequential and local memory access, which is more cache-friendly and ideal for systems with non-uniform memory access (NUMA). It avoids division operations by relying on additions and subtractions, making it suitable for low-level or embedded systems with limited arithmetic capabilities.

Q. Why does Fibonacci Search use the Fibonacci sequence instead of halving the array like Binary Search?

Fibonacci Search uses the Fibonacci sequence to determine the optimal index for comparison because it allows splitting the array in a way that ensures balanced comparisons, just like Binary Search, but with less computational overhead. The nature of the Fibonacci sequence supports index calculation using only addition and subtraction, avoiding division altogether. This is particularly beneficial in environments where division operations are expensive or unavailable.

Q. Is Fibonacci Search suitable for all types of data structures?

No, Fibonacci Search is only applicable to sorted arrays. Like Binary Search, it requires a dataset to be sorted in ascending (or descending) order to function correctly. It is not applicable to unsorted arrays, linked lists, or tree-based structures. Moreover, its benefits are more pronounced in systems with non-uniform memory latency, so it may not outperform Binary Search in general-purpose RAM-based systems with uniform access times.

Q. What is the time complexity of Fibonacci Search, and how does it compare to Binary Search?

The time complexity of Fibonacci Search is O(log n), which is the same as Binary Search. However, the number of arithmetic operations and memory accesses may differ. Fibonacci Search often has slightly more comparisons in practice but compensates with better memory access patterns in certain hardware environments. The constant factors can vary based on the specific implementation and system architecture.

Q. When should Fibonacci Search be preferred over other search algorithms like Binary Search or Interpolation Search?

Fibonacci Search should be considered when:

• The dataset is sorted.
• The system exhibits non-uniform memory access patterns.
• The platform lacks efficient division operations (e.g., microcontrollers).
• You're working with tape-based or sequential storage where minimal memory jumps are critical.
• You want to maximize cache locality and reduce access latency.

In contrast, Binary Search is preferred for general-purpose use on RAM, and Interpolation Search is better for datasets with uniformly distributed elements.

Suggested Reads: 

1. Difference Between Hashing And Encryption Decoded
2. 53 Frequently Asked Linked List Interview Questions With Answers 2024
3. Data Structure Interview Questions For 2024 [With Detailed Answers]
4. Tree Topology | Advantages & Disadvantages In Computer Network
5. Decoding Data Redundancy In DBMS| Causes, Advantages, Solutions