searches.fibonacci_search

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

Functions

fibonacci(→ int)	Finds fibonacci number in index k.
fibonacci_search(→ int)	A pure Python implementation of a fibonacci search algorithm.

Module Contents

searches.fibonacci_search.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.

searches.fibonacci_search.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