searches.fibonacci_search
=========================

.. py:module:: searches.fibonacci_search

.. autoapi-nested-parse::

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

.. autoapisummary::

   searches.fibonacci_search.fibonacci
   searches.fibonacci_search.fibonacci_search


Module Contents
---------------

.. py:function:: 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.


.. py:function:: 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