iframe-proxy | Sunbelt Computer Software

History

132 lines (116 loc) · 2.93 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

"""

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)

>>> fibonacci(2)

>>> fibonacci(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)

>>> fibonacci_search([4, 5, 6, 7], -10)

-1

>>> fibonacci_search([-18, 2], -18)

>>> fibonacci_search([5], 5)

>>> fibonacci_search(['a', 'c', 'd'], 'c')

>>> fibonacci_search(['a', 'c', 'd'], 'f')

-1

>>> fibonacci_search([], 1)

-1

>>> fibonacci_search([.1, .4 , 7], .4)

>>> fibonacci_search([], 9)

-1

>>> fibonacci_search(list(range(100)), 63)

>>> fibonacci_search(list(range(100)), 99)

>>> fibonacci_search(list(range(-100, 100, 3)), -97)

>>> fibonacci_search(list(range(-100, 100, 3)), 0)

-1

>>> fibonacci_search(list(range(-100, 100, 5)), 0)

>>> fibonacci_search(list(range(-100, 100, 5)), 95)

"""

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()

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

fibonacci_search.py

Latest commit

History

fibonacci_search.py

File metadata and controls