Divide and Conquer: Fibonacci Search | in Python

We will implement the Fibonacci Search algorithm, the basic idea behind this is to use the fibonacci numbers to divide the array into smaller and smaller subarrays until the target element is found.

Photo by Faris Mohammed on Unsplash

Fibonacci numbers

Are a sequence of numbers in which each number is the sum of the two preceding numbers, starting from 0 and 1.

The first few numbers in the sequence are:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, …

The Fibonacci sequence has numerous interesting properties and appears in various areas of mathematics and science, including computer science and biology.

It is used in many algorithms, including the Fibonacci search algorithm, to optimize performance by taking advantage of the mathematical properties of the sequence.

Search Algorithms

Search algorithms are a class of algorithms that are used to search for a particular value or set of values in a dataset. The goal of a search algorithm is to efficiently locate the target value(s) in the dataset, and to return the location(s) or some other information about the value(s).

There are several different types of search algorithms, each with its own advantages and disadvantages. Some of the most commonly used search algorithms include:

1. Linear search: This is the simplest type of search algorithm, which involves iterating through the entire dataset one element at a time, and comparing each element to the target value. It is not efficient for large datasets, but can be useful for small datasets or for cases where the data is not sorted.
2. Binary search: This is a more efficient search algorithm that requires the data to be sorted in advance. It works by repeatedly dividing the search range in half, and determining which half the target value is in, until the target value is found or it is determined that the value is not in the dataset.
3. Hash search: This is a search algorithm that involves using a hash function to convert the target value into an index into a data structure (such as an array or a hash table), where the target value can be found. This algorithm can be very efficient for large datasets, but requires a well-designed hash function to avoid collisions.
4. Tree-based search: This is a search algorithm that involves using a tree data structure (such as a binary search tree or a B-tree) to store the dataset. The target value is then located by traversing the tree from the root node, following branches based on comparisons between the target value and the values stored in the tree.
5. Fibonacci search: below

There are many other types of search algorithms as well, each with its own strengths and weaknesses. The choice of algorithm to use will depend on factors such as the size of the dataset, the speed of access to the data, and the properties of the target value (e.g. whether it is unique or not).

Fibonacci Search

Fibonacci search is a search algorithm that uses the Fibonacci sequence to search for an element in a sorted list. It is a divide and conquer algorithm that works by dividing the list into smaller sublists using the Fibonacci sequence.

The function takes two arguments:

• arr: A list of sorted elements in which we want to search for the element val.
• val: The element we want to find in the list.

If the list is not sorted, we have to sort it, otherwise it will not work.

The function returns the index of the element val in the list arr, or -1 if val is not found in the list.

The function works by first finding the largest Fibonacci number less than or equal to the length of the list arr. It does this by computing the Fibonacci numbers in sequence until it finds the first number that is greater than or equal to the length of the list.

Once it has found, the function uses it as a starting point for the search.

It sets the variable fibb_k to this Fibonacci number and offset to 0.

The function then enters a loop that continues as long as fibb_k is greater than 0.

In each iteration of the loop, the function checks whether the element at the index offset + fibonacci(fibb_k - 1) is equal to val.

If it is, the function returns that index.

If the element at that index is greater than val, the function reduces fibb_k by 1 and continues the loop.

If the element at that index is less than val, the function increases offset by fibonacci(fibb_k - 1) and reduces fibb_k by 2. It then continues the loop.

If the loop exits without finding val, the function returns -1 to indicate that the element was not found in the list.

Fibonacci search has a time complexity of O(log n) and can be faster than binary search in some cases, especially when the data is not uniformly distributed.

However, it requires precomputing the Fibonacci sequence and can be slower than binary search when the data is uniformly distributed.

The Code:

"""
This is pure Python implementation of fibonacci search.
Resources used:
https://en.wikipedia.org/wiki/Fibonacci_search_technique
For doctests run following command:
python3 -m doctest -v fibonacci_search.py
For manual testing run:
python3 fibonacci_search.py
"""
from functools import lru_cache


@lru_cache
def fibonacci(k: int) -> int:
    """Finds fibonacci number in index k.
    Parameters
    ----------
    k :
        Index of fibonacci.
    Returns
    -------
    int
        Fibonacci number in position k.
    >>> fibonacci(0)
    0
    >>> fibonacci(2)
    1
    >>> fibonacci(5)
    5
    >>> fibonacci(15)
    610
    >>> fibonacci('a')
    Traceback (most recent call last):
    TypeError: k must be an integer.
    >>> fibonacci(-5)
    Traceback (most recent call last):
    ValueError: k integer must be greater or equal to zero.
    """
    if not isinstance(k, int):
        raise TypeError("k must be an integer.")
    if k < 0:
        raise ValueError("k integer must be greater or equal to zero.")
    if k == 0:
        return 0
    elif k == 1:
        return 1
    else:
        return fibonacci(k - 1) + fibonacci(k - 2)


def fibonacci_search(arr: list, val: int) -> int:
    """A pure Python implementation of a fibonacci search algorithm.
    Parameters
    ----------
    arr
        List of sorted elements.
    val
        Element to search in list.
    Returns
    -------
    int
        The index of the element in the array.
        -1 if the element is not found.
    >>> fibonacci_search([4, 5, 6, 7], 4)
    0
    >>> fibonacci_search([4, 5, 6, 7], -10)
    -1
    >>> fibonacci_search([-18, 2], -18)
    0
    >>> fibonacci_search([5], 5)
    0
    >>> fibonacci_search(['a', 'c', 'd'], 'c')
    1
    >>> fibonacci_search(['a', 'c', 'd'], 'f')
    -1
    >>> fibonacci_search([], 1)
    -1
    >>> fibonacci_search([.1, .4 , 7], .4)
    1
    >>> fibonacci_search([], 9)
    -1
    >>> fibonacci_search(list(range(100)), 63)
    63
    >>> fibonacci_search(list(range(100)), 99)
    99
    >>> fibonacci_search(list(range(-100, 100, 3)), -97)
    1
    >>> fibonacci_search(list(range(-100, 100, 3)), 0)
    -1
    >>> fibonacci_search(list(range(-100, 100, 5)), 0)
    20
    >>> fibonacci_search(list(range(-100, 100, 5)), 95)
    39
    """
    len_list = len(arr)
    # Find m such that F_m >= n where F_i is the i_th fibonacci number.
    i = 0
    while True:
        if fibonacci(i) >= len_list:
            fibb_k = i
            break
        i += 1
    offset = 0
    while fibb_k > 0:
        index_k = min(
            offset + fibonacci(fibb_k - 1), len_list - 1)  # Prevent out of range
        item_k_1 = arr[index_k]
        if item_k_1 == val:
            return index_k
        elif val < item_k_1:
            fibb_k -= 1
        elif val > item_k_1:
            offset += fibonacci(fibb_k - 1)
            fibb_k -= 2
    else:
        return -1


if __name__ == "__main__":
    import doctest

    doctest.testmod()

fibb_k is the index of the largest Fibonacci number F_m that is less than or equal to the length of the input array arr. In other words, F_{fibb_k} <= len(arr). This value is found using a binary search-like technique where the Fibonacci sequence is generated and its terms are checked against the length of the input array until the largest term that is less than or equal to the length is found.

The variable index_k represents the index in the input list arr that corresponds to the current estimate of the location of the search value. The value of index_k is computed based on the current Fibonacci number being used in the search and the current offset within the input list. The value is then checked to ensure it is not out of range of the list before being used to retrieve the corresponding element from the list, which is then compared to the search value.

In the given code, item_k_1 is a variable that stores the value of an element in the array at the index obtained by using the Fibonacci search algorithm. Specifically, it stores the value of the element at index k-1 where k is the current index calculated using the Fibonacci search algorithm. This value is compared with the value to be searched, and the search algorithm continues to search for the value in the array using the Fibonacci search approach.

Step-by-step:

Visualization of how the Fibonacci search algorithm works for the test case fibonacci_search([4, 5, 6, 7], -10):

1. Initialize the array arr and the value to search for val.

arr = [4, 5, 6, 7]

val = -10

2. Find the smallest Fibonacci number F_k that is greater than or equal to the length of the array arr.

• In this case, len(arr) = 4, so we need to find the smallest Fibonacci number that is greater than or equal to 4.
• The Fibonacci sequence is: 0, 1, 1, 2, 3, 5, 8, 13, ...
• The smallest Fibonacci number that is greater than or equal to 4 is 5 (F_5 = 5).

3. Initialize variables offset and F_m to 0 and F_k respectively.

• offset = 0
• F_m = F_k = 5

4. Compare the search value val with the element arr[F_{k-1}] and do the following:

• Since val < arr[F_{k-1}] (-10 < 4), set F_k = F_{k-1} and F_{k-1} = F_{k-2}.
• This means that F_k = 3, F_{k-1} = 2, and offset remains 0.

5. Compute the new index to search as i = offset + F_{k-1}.

• In this case, i = 2.

6. Check if the search value val is equal to the element at index i in the array arr.

• In this case, arr[i] = arr[2] = 6 and val = -10, so they are not equal.

7. If val < arr[i], set F_k = F_{k-2}, F_{k-1} = F_{k-3}, and keep the same offset.

• This means that F_k = 2, F_{k-1} = 1, and offset remains 0.

8. If val > arr[i], set F_k = F_{k-1}, F_{k-1} = F_{k-2}, and update the offset.

• This means that F_k = 1, F_{k-1} = 1, and offset = 2.

9 Repeat steps 5–8 until the search value is found or there are no more elements to check.

• In this case, the search value -10 is not found in the array, so the function returns -1.

Fibonacci vs Binary Search

1. Fibonacci search requires more pre-processing than binary search. In Fibonacci search, we need to calculate Fibonacci numbers, while in binary search, we only need to sort the input array.
2. Fibonacci search has better performance than binary search when the input array is very large, but the number of elements to be searched is small. In this case, the time complexity of Fibonacci search is O(log n), while binary search has a time complexity of O(log n) as well.
3. Binary search is faster than Fibonacci search when the input array is small or the number of elements to be searched is large. In this case, binary search has a time complexity of O(log n), while Fibonacci search has a time complexity of O(log n) and may perform more calculations.
4. Fibonacci search has better space complexity than binary search, as it does not require any additional storage beyond the input array.

In general, both search algorithms are effective and efficient, and the choice between them depends on the size of the input array and the number of elements to be searched.

Fibonacci Search

Bogdan Tudorache | Founder @ berrynews.org

If you like the article and would like to support me, make sure to:

👏 Clap for the story (50 Claps) to help this article be featured

🔔 Follow me Bogdan Tudorache

📰 Read more coding content on Coding Challenge

🔔 Connect w/ me: LinkedIn | Reddit