Fibonacci Search Algorithm - Computer Geek (2024)

Distribute Education like Computer Geek

What is Fibonacci Sequence?

.

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1.

It is named after the Italian mathematician Leonardo of Pisa, known as Fibonacci, who introduced the sequence to Western mathematics in his book “Liber Abaci” in 1202.

The Fibonacci sequence typically begins with the numbers 0 and 1, and each subsequent number is generated by adding the two previous numbers. The sequence starts as follows:

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

.

Here’s how the sequence continues to develop

0 + 1 = 1

1 + 1 = 2

1 + 2 = 3

2 + 3 = 5

3 + 5 = 8

5 + 8 = 13

8 + 13 = 21

13 + 21 = 34

And so on…

.

Definition of Fibonacci Search

1. Fibonacci Search is an algorithm used to locate a specific element within a sorted array or list with Fibonacci numbers.
2. It is based on the Fibonacci sequence, a series of numbers where each number is the sum of the two preceding ones (e.g., 0, 1, 1, 2, 3, 5, 8, 13, 21, …) that I said it earlier.
3. The key idea is to use the Fibonacci numbers to define two pointers ‘left’ and ‘right’, within the array, which are then adjusted based on comparisons with the target element until the element is found or it is determined that the element does not exist in the sorted array.
4. Fibonacci Search method is yet another elimination method where a portion of the input array is eliminated.
5. Fibonacci Search is known for its time efficiency, typically having a time complexity of O(log n) for searching in sorted datasets, making it suitable for large arrays or lists. However, it requires the data to be sorted in ascending order for effective operation.

Algorithm for Fibonacci Search

1. Input a sorted array A[i] with n numbers 
and target element which we want to search for.

2. Start by generating a series of Fibonacci
numbers until you find a number that is greater
than or equal to the length of the array.
F(k) >= n

Example – if n = 10
Then, fibonacci sequence we have is
0, 1, 1, 2, 3, 5, 8, 13, because 13 >= 10.

3. If F(k) = 0, then stop and print the message
as element not found.

4. Name a variable “offset” = -1

5. Check index i = min(offset + F(k-2), n-1)

6. Compare

If Target Element = A[i],

return i and stop the search

If Target Element > A[i],

k = k-1, offset = i,

repeat step 5 and 6.

If Target Element < A[i],

k = k-2, repeat step 5 and 6.

.

How does it work?

1. Suppose you have a sorted array and you want to find the number `15`.

.

2. Generate the Fibonacci sequence where F(k) >= n = 11.

3. F(k) ≠ 0, then search continues
4. Make a variable ‘offset = -1’.

.

Iteration 1

Check i = min (offset + F(k-2), n-1), where k = 7, offset = -1, n = 11

i = min ( -1 + 5, 10)

i = min (4, 10) = 4

Compare the Target Element to Sorted Array

• Target Element = 15, A[4] = 9
• Do k = k-1, offset = 4 and again check for i.

.

Iteration 2

Check i = min (offset + F(k-2), n-1) where k = 6, offset = 4, n = 11.

i = min (4 + 3, 10)

i = min (7, 10) = 7

Compare the Target Element to Sorted Array

• Target Element = 15, A[7] = 15
• Search is successful and return i = 7, the index of the sorted array in which we found Target Element.

.

Source Code for Fibonacci Search

Time Complexity of Fibonacci Search

1. In the best-case, the target element is found at the very beginning of the search process, typically after only a few comparisons. The best-case time complexity is O(1), as the algorithm may find the target element with just a single comparison.
2. The average-case time complexity of Fibonacci Search is O(log n), where n is the number of elements in the sorted array. On average, the algorithm efficiently reduces the search space by approximately half in each comparison, similar to binary search. This is achieved by using the Fibonacci sequence to determine the positions to check.

3. The worst-case time complexity of Fibonacci Search is also O(log n). While it may seem surprising, the worst-case occurs when the algorithm repeatedly moves two steps left in the Fibonacci sequence. Even in this scenario, the search space is effectively reduced, leading to a logarithmic time complexity. This worst-case behavior is still significantly more efficient than linear search (O(n)) for large datasets.

.

Space complexity of Fibonacci Search

1. The space complexity of the Fibonacci Search algorithm is O(1), which means it uses a constant amount of extra space for variables regardless of the size of the input array.
2. This constant space usage is due to the fact that the algorithm maintains a fixed number of variables to store indices, offsets, and Fibonacci numbers during the search process. The space required by the algorithm does not grow with the size of the input array, making it space-efficient even for large datasets.

.

Advantages of Fibonacci Search

1. Efficient for searching in sorted arrays.
2. Logarithmic time complexity, making it fast for large datasets.
3. Minimal memory usage (O(1)).
4. Adaptable by adjusting Fibonacci numbers.
5. In some cases, it is faster than binary search.

.

Disadvantages of Fibonacci Search

1. Requires the array to be sorted.
2. Complex to implement compared to linear search and binary search.

.

Applications of Fibonacci Search

1. Fibonacci Search can be used in search engines and database management systems to quickly locate documents, records, or entries in sorted collections.
2. Library databases often store books, journals, and other resources in sorted order. Fibonacci Search can help users find specific titles or authors efficiently.
3. Economic data, such as stock prices or financial records, is frequently sorted. Fibonacci Search can assist in finding historical data points or specific financial information.
4. Geographic data, such as maps and spatial information, is often sorted by location or coordinates.
5. Some data compression algorithms utilize Fibonacci sequences to represent compressed data efficiently.
6. When a data packet needs to be routed to a specific destination, the network router or switch must perform a lookup in the routing table to identify the appropriate route. Fibonacci Search can be employed to efficiently search within the sorted routing table.

Q8- What is the role of the offset variable in the Fibonacci Search algorithm?

1. It stores the target element.

2. It tracks the number of iterations.

3. It determines the starting point for comparisons.

4. It calculates the Fibonacci sequence.

Q9- What is the space complexity of the Fibonacci Search algorithm?

1. O(log n)

2. O(n)

3. O(1)

4. O(n log n)

Q10- In which real-world scenario might Fibonacci Search be useful?

1. Analyzing unsorted data in a spreadsheet

2. Searching for a contact in a phone book

3. Sorting a large dataset

4. Generating random numbers

Q11- What is the Fibonacci sequence primarily used for in computer science and mathematics?

1. Generating prime numbers

2. Calculating square roots

3. Sorting algorithms

4. Modeling growth and sequences in various fields

BOOKS