Introduction to Fibonacci Search Algorithm

The Fibonacci Search algorithm takes a unique approach to efficiently locating elements within a sorted array. Unlike traditional binary search, which divides the array into halves, Fibonacci Search divides the array into segments based on Fibonacci numbers’ ratios. By leveraging the properties of Fibonacci numbers, it balances narrowing down the search space. This algorithm begins by initializing two Fibonacci numbers, fibM, and fibMMinus1, to define the search range. Then, it iteratively adjusts these numbers and updates offsets until finding the desired element or concludes the search unsuccessfully. Fibonacci Search is not just unique, and it also brings significant advantages. It can handle large arrays without a predetermined size, ensuring a more evenly distributed search space than binary search. However, it may involve additional computational overhead compared to binary search for smaller arrays.

Introduction

How Fibonacci Search Works

Fibonacci Search functions partition the search area evenly, employing the ratios derived from Fibonacci numbers. Below is a detailed breakdown of the algorithm’s operation:

Initialization:
Initialize two Fibonacci numbers, fibM, and fibMMinus1, so fibM is the smallest Fibonacci number greater than or equal to the array’s length.

fibM=fibMMinus1+fibMMinus2

fibMMinus1=fibM−fibMMinus2

Initialize fibMMinus2=0 and fibMMinus1=1.

Calculate fibM using the above formulas until fibM≥length of array.

Define Offsets:

Define offset1 and offset2 offsets to delineate the range of the subarray under scrutiny. Initially, assign offset1 the value 0 and offset2 the array length minus 1.

Search Process:

Compare the target element with the element located at index offset1 + fibMMinus1.
If the target is greater than the element at this index, update offset1 to offset1 + fibMMinus1 and offset2 to offset1 + fibM.
If the target is smaller, update offset2 to offset1 + fibMMinus1 and recalculate fibM and fibMMinus1
Repeat these steps until finding the target element or the search range is exhausted.
For searching the upper half: offset1 = offset1+fibMMinus1 and offset2 = offset1 + fibM.
For searching in the lower half: offset2 = offset1+fibMMinus1 and recalculate fibM and fibMMinus1.

Termination:

Persist in the search process until fibM reduces to 1. Return this index if it finds the target element at the index offset1 + fibMMinus1. If not, conclude that the component is absent from the array.

Key Points:

It ensures a more balanced search space than binary search.
It uses Fibonacci numbers’ ratios to determine the following search range, leading to efficient search operations.
The algorithm adjusts the search range until it finds the target element or determines its absence.

Implementation

Given a sorted array:

Initialize Fibonacci Numbers:

We need Fibonacci numbers up to a value greater than or equal to the array length (n = 11).

i.e., FibM(i)>n [array size]

So, FibM(i) = FibM(i-1) + FibM(i-2)

FibM(0) = 0, FibM(0) < 11

FibM(1) = 1, FibM(1) < 11

FibM(2) = 1, FibM(2) < 11

FibM(3) = 2, FibM(3) < 11

FibM(4) = 3, FibM(4) < 11

FibM(5) = 5, FibM(5) < 11

FibM(6) = 8, FibM(6) < 11

FibM(7) = 13, FibM(7) > 11 (First Smallest Fibonacci number which is greater than n)

So, the FibM(7) = 13 is the Fibonacci number greater than the array size. Now, we will define all the values, putting offset = 0 initially:

FibM = 13, FibM1 = 8, FibM2 = 5, Offset = 0

So, i = min(offset+FibM2, n-1) = min(0+5, 10) = min(5,10)

Hence, i = 5, the index we get is 5.

So, the array element at the index value 5 is 50, which is:

arr[5] = 50

Comparing Target with the Element

After the calculations, we get the index i=5, so arr[5] = 50. But still, our target is 85, so arr[5] = 50 < 85 (Target).

Narrow the Search Space Based on the Comparison

Our target is 85, and we compared our searched array element at the index value 5. So now we will narrow down the search space excluding the left half element.

Search Process

Before the search process, update all the values once again:

Previously, FibM = 13, FibM1 = 8, FibM2 = 5. Now, we will go one step back in the Fibonacci series.

The updated values are FibM = 8, FibM1 = 5, and FibM2 = 3, and our new offset will be 5.

So,

FibM = 8, FibM1 = 5, FibM2 =3, Offset = 5

i = min(offset+FibM2, n-1) = min(5+3, 10) = min(8,10)

So, i = 8 = arr[8] = 85 = Target

In the Last Comparison, the target element matches the searched element, and the search process will terminate at this part.

So, element 85 is found at index 8.

Pseudocode

function fibonacci_search(arr, x):
    n = length(arr)
    fibM_minus_2 = 0
    fibM_minus_1 = 1
    fibM = fibM_minus_1 + fibM_minus_2

    while (fibM < n): fibM_minus_2 = fibM_minus_1 fibM_minus_1 = fibM fibM = fibM_minus_1 + fibM_minus_2 offset = -1 // Search within the array until the range reduces to 1 while (fibM > 1):
        i = min(offset + fibM_minus_2, n - 1)
        // If x is greater than the element at index i, update offset and Fibonacci numbers
        if (arr[i] < x): fibM = fibM_minus_1 fibM_minus_1 = fibM_minus_2 fibM_minus_2 = fibM - fibM_minus_1 offset = i // If x is smaller, update offset and Fibonacci numbers elif (arr[i] > x):
            fibM = fibM_minus_2
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        // If x is found, return the index
        else:
            return i

    // Check if the last element is x
    if (fibM_minus_1 and arr[offset + 1] == x):
        return offset + 1

    // Element not found
    return -1

Explanation:

The fibonacci_search function accepts two parameters: an array arr and a target element x.
It begins by setting up Fibonacci numbers (fibM, fibM_minus_1, fibM_minus_2) to identify the smallest Fibonacci number greater than or equal to the array’s length.
Using these Fibonacci numbers, it searches within the array, progressively narrowing down the search range until it reduces to a single element, updating offsets and Fibonacci numbers as necessary.
If it discovers the target element x during the search, the function returns its index; otherwise, it returns -1 to signify that the element is not present in the array.

Complexity Analysis

Time Complexity:

It exhibits a time complexity of O(log n), n represents the number of elements in the array.
This complexity emerges because the search space halves roughly with each step, akin to binary search.
Thanks to the exponential growth of Fibonacci numbers, the algorithm achieves a balanced division of the search space, leading to logarithmic time complexity.

Space Complexity:

It exhibits a time complexity akin to binary search, rendering it efficient for sorted array searches.
Its equitable division of the search area guarantees a logarithmic time complexity, even with sizable input arrays.
Moreover, its space complexity remains fixed, rendering it appropriate for environments with limited memory resources.

Example

Code:

def fibonacci_search(arr, x):
    n = len(arr)
    fibM_minus_2 = 0
    fibM_minus_1 = 1
    fibM = fibM_minus_1 + fibM_minus_2

    while fibM < n: fibM_minus_2, fibM_minus_1 = fibM_minus_1, fibM fibM = fibM_minus_1 + fibM_minus_2 offset = -1 while fibM > 1:
        i = min(offset + fibM_minus_2, n - 1)
        if arr[i] < x: fibM, fibM_minus_1 = fibM_minus_1, fibM_minus_2 fibM_minus_2 = fibM - fibM_minus_1 offset = i elif arr[i] > x:
            fibM_minus_2, fibM_minus_1 = fibM_minus_1 - fibM_minus_2, fibM_minus_2
            fibM = fibM - fibM_minus_1
        else:
            return i

    if fibM_minus_1 and arr[offset + 1] == x:
        return offset + 1
    return -1

# Example usage with a different array:
arr = [2, 5, 7, 12, 15, 17, 22, 25, 27, 30]
x = 22
result = fibonacci_search(arr, x)
if result != -1:
    print("Element found at index:", result)
else:
    print("Element not found")

Output:

Time Complexity:

The Time Complexity of this example is O(log n).

Pros and Cons of Fibonacci Search

Pros

Efficient Search:

It efficiently locates elements within sorted arrays, which is particularly advantageous when dealing with arrays of unknown or considerable sizes.
Its capability to evenly distribute the search space ensures optimal search times.

Adaptability to Array Size:

In contrast to binary search, Fibonacci Search operates without requiring prior knowledge of the array’s size.
It effectively accommodates arrays of varying sizes by dynamically adjusting the search space based on Fibonacci numbers’ ratios.

No Preprocessing Required:

Implementing Fibonacci Search does not demand any preprocessing steps for the array, simplifying the process significantly.

Improved Performance for Large Arrays:

It excel in scenarios involving large arrays, surpassing alternative search algorithms with its balanced search space division strategy.

Cons

Additional Computational Overhead:

It entails extra computational steps to compute Fibonacci numbers and adjust offsets. This step may introduce increased overhead compared to simpler search algorithms like binary search, which is especially noticeable for smaller arrays.

Limited Utility for Small Arrays:

In the case of smaller arrays, Fibonacci Search may not yield significant performance advantages over alternative search methods due to its added computational complexity.

Unsuitability for Unsorted Arrays:

It necessitates that the input array be pre-sorted, restricting its applicability to situations where the array is already in sorted order.

Potential for Inefficient Space Division:

Under certain circumstances, Fibonacci Search may exhibit inefficient division of the search space, leading to prolonged search times compared to binary search.

Real World Applications

Information Retrieval Systems: In large databases or search engines, Fibonacci Search can efficiently locate relevant information based on queries, especially when the database size is unknown or dynamic.
Financial Markets: Traders can employ Fibonacci Search to recognize patterns or trends in stock prices or other financial data, assisting them in making well-informed decisions.
Data Analysis: It can assist in data analysis tasks, such as finding specific data points within large datasets or searching for patterns in time-series data.
Genetics and Bioinformatics: In genetics, researchers can use the Fibonacci Search to find specific gene sequences or patterns within DNA or protein sequences.
Computer Graphics: It can be employed in computer graphics algorithms, such as ray tracing or collision detection, to search for intersections or determine visibility efficiently.
Optimization Problems: You can apply Fibonacci Search to optimization problems, such as minimizing/maximizing functions or finding optimal solutions in engineering or logistics.
Robotics: It can aid in robotics applications, such as path planning or localization, by efficiently searching for optimal routes or determining the robot’s position relative to known landmarks.
Image Processing: In image processing tasks, Fibonacci Search can be used for feature detection, object recognition, or image registration, facilitating efficient searching within image datasets.

Conclusion

It emerge as a valuable algorithm for efficiently locating elements within sorted arrays. Its systematic division of the search space, driven by Fibonacci numbers’ ratios, ensures optimal search performance, especially in scenarios with unknown or significant array sizes. Although Fibonacci Search may involve additional computational complexity compared to simpler algorithms, its versatility in handling diverse array sizes and large datasets makes it applicable across various domains. Despite its limitations, such as needing pre-sorted arrays, Fibonacci Search remains a dependable option for tasks prioritizing efficient element retrieval. Overall, Fibonacci Search represents a robust solution for real-world search problems, striking a balance between computational efficiency and adaptability.

Frequently Asked Questions (FAQs)

Q1. When is Fibonacci Search preferable over binary search?

Answer: It becomes advantageous in scenarios where the array size is uncertain or extensive because it adapts the search space dynamically using Fibonacci numbers. It also proves beneficial when the array doesn’t neatly divide into halves, a limitation often encountered with binary search.

Q2. How does Fibonacci Search handle arrays with unknown sizes?

Answer: It adapts the search space by leveraging Fibonacci numbers’ ratios, making it suitable for arrays with uncertain or changing sizes. The algorithm persists in the search until it encounters a Fibonacci number equal to or exceeding the array’s size.

Q3. How can one optimize the Fibonacci Search for better performance?

Answer: Optimizations such as caching Fibonacci numbers or using iterative approaches instead of recursive ones can improve Fibonacci Search’s performance, especially for large arrays. Additionally, considering alternative search algorithms based on the specific characteristics of the problem may be beneficial.

Q4. Does Fibonacci Search always perform better than binary search?

Answer: It does not always outperform binary search. Although Fibonacci Search may excel in uncertain or fluctuating array sizes, binary search might prove superior for specific array sizes and search criteria. It’s crucial to carefully evaluate the problem’s unique attributes to determine the most suitable algorithm.

Quiz Result
Total Questions	Correct Answers	Wrong Answers	Percentage

Introduction to Fibonacci Search Algorithm

Table of Contents

How Fibonacci Search Works

Key Points:

Implementation

Pseudocode

Complexity Analysis

Example

Pros and Cons of Fibonacci Search

Pros

Cons

Real World Applications

Conclusion

Frequently Asked Questions (FAQs)

Recommended Articles

Follow us!

APPS

Blog

Courses

Email