TheAlgorithms-Python

1
"""
2
This is pure Python implementation of fibonacci search.
3

4
Resources used:
5
https://en.wikipedia.org/wiki/Fibonacci_search_technique
6

7
For doctests run following command:
8
python3 -m doctest -v fibonacci_search.py
9

10
For manual testing run:
11
python3 fibonacci_search.py
12
"""
13

14
from functools import lru_cache
15

16

17
@lru_cache
18
def fibonacci(k: int) -> int:
19
    """Finds fibonacci number in index k.
20

21
    Parameters
22
    ----------
23
    k :
24
        Index of fibonacci.
25

26
    Returns
27
    -------
28
    int
29
        Fibonacci number in position k.
30

31
    >>> fibonacci(0)
32
    0
33
    >>> fibonacci(2)
34
    1
35
    >>> fibonacci(5)
36
    5
37
    >>> fibonacci(15)
38
    610
39
    >>> fibonacci('a')
40
    Traceback (most recent call last):
41
    TypeError: k must be an integer.
42
    >>> fibonacci(-5)
43
    Traceback (most recent call last):
44
    ValueError: k integer must be greater or equal to zero.
45
    """
46
    if not isinstance(k, int):
47
        raise TypeError("k must be an integer.")
48
    if k < 0:
49
        raise ValueError("k integer must be greater or equal to zero.")
50
    if k == 0:
51
        return 0
52
    elif k == 1:
53
        return 1
54
    else:
55
        return fibonacci(k - 1) + fibonacci(k - 2)
56

57

58
def fibonacci_search(arr: list, val: int) -> int:
59
    """A pure Python implementation of a fibonacci search algorithm.
60

61
    Parameters
62
    ----------
63
    arr
64
        List of sorted elements.
65
    val
66
        Element to search in list.
67

68
    Returns
69
    -------
70
    int
71
        The index of the element in the array.
72
        -1 if the element is not found.
73

74
    >>> fibonacci_search([4, 5, 6, 7], 4)
75
    0
76
    >>> fibonacci_search([4, 5, 6, 7], -10)
77
    -1
78
    >>> fibonacci_search([-18, 2], -18)
79
    0
80
    >>> fibonacci_search([5], 5)
81
    0
82
    >>> fibonacci_search(['a', 'c', 'd'], 'c')
83
    1
84
    >>> fibonacci_search(['a', 'c', 'd'], 'f')
85
    -1
86
    >>> fibonacci_search([], 1)
87
    -1
88
    >>> fibonacci_search([.1, .4 , 7], .4)
89
    1
90
    >>> fibonacci_search([], 9)
91
    -1
92
    >>> fibonacci_search(list(range(100)), 63)
93
    63
94
    >>> fibonacci_search(list(range(100)), 99)
95
    99
96
    >>> fibonacci_search(list(range(-100, 100, 3)), -97)
97
    1
98
    >>> fibonacci_search(list(range(-100, 100, 3)), 0)
99
    -1
100
    >>> fibonacci_search(list(range(-100, 100, 5)), 0)
101
    20
102
    >>> fibonacci_search(list(range(-100, 100, 5)), 95)
103
    39
104
    """
105
    len_list = len(arr)
106
    # Find m such that F_m >= n where F_i is the i_th fibonacci number.
107
    i = 0
108
    while True:
109
        if fibonacci(i) >= len_list:
110
            fibb_k = i
111
            break
112
        i += 1
113
    offset = 0
114
    while fibb_k > 0:
115
        index_k = min(
116
            offset + fibonacci(fibb_k - 1), len_list - 1
117
        )  # Prevent out of range
118
        item_k_1 = arr[index_k]
119
        if item_k_1 == val:
120
            return index_k
121
        elif val < item_k_1:
122
            fibb_k -= 1
123
        elif val > item_k_1:
124
            offset += fibonacci(fibb_k - 1)
125
            fibb_k -= 2
126
    return -1
127

128

129
if __name__ == "__main__":
130
    import doctest
131

132
    doctest.testmod()
133