searches.ternary_search
=======================

.. py:module:: searches.ternary_search

.. autoapi-nested-parse::

   This is a type of divide and conquer algorithm which divides the search space into
   3 parts and finds the target value based on the property of the array or list
   (usually monotonic property).

   Time Complexity  : O(log3 N)
   Space Complexity : O(1)



Attributes
----------

.. autoapisummary::

   searches.ternary_search.precision
   searches.ternary_search.user_input


Functions
---------

.. autoapisummary::

   searches.ternary_search.ite_ternary_search
   searches.ternary_search.lin_search
   searches.ternary_search.rec_ternary_search


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

.. py:function:: ite_ternary_search(array: list[int], target: int) -> int

   Iterative method of the ternary search algorithm.
   >>> test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42]
   >>> ite_ternary_search(test_list, 3)
   -1
   >>> ite_ternary_search(test_list, 13)
   4
   >>> ite_ternary_search([4, 5, 6, 7], 4)
   0
   >>> ite_ternary_search([4, 5, 6, 7], -10)
   -1
   >>> ite_ternary_search([-18, 2], -18)
   0
   >>> ite_ternary_search([5], 5)
   0
   >>> ite_ternary_search(['a', 'c', 'd'], 'c')
   1
   >>> ite_ternary_search(['a', 'c', 'd'], 'f')
   -1
   >>> ite_ternary_search([], 1)
   -1
   >>> ite_ternary_search([.1, .4 , -.1], .1)
   0


.. py:function:: lin_search(left: int, right: int, array: list[int], target: int) -> int

   Perform linear search in list. Returns -1 if element is not found.

   Parameters
   ----------
   left : int
       left index bound.
   right : int
       right index bound.
   array : List[int]
       List of elements to be searched on
   target : int
       Element that is searched

   Returns
   -------
   int
       index of element that is looked for.

   Examples
   --------
   >>> lin_search(0, 4, [4, 5, 6, 7], 7)
   3
   >>> lin_search(0, 3, [4, 5, 6, 7], 7)
   -1
   >>> lin_search(0, 2, [-18, 2], -18)
   0
   >>> lin_search(0, 1, [5], 5)
   0
   >>> lin_search(0, 3, ['a', 'c', 'd'], 'c')
   1
   >>> lin_search(0, 3, [.1, .4 , -.1], .1)
   0
   >>> lin_search(0, 3, [.1, .4 , -.1], -.1)
   2


.. py:function:: rec_ternary_search(left: int, right: int, array: list[int], target: int) -> int

   Recursive method of the ternary search algorithm.

   >>> test_list = [0, 1, 2, 8, 13, 17, 19, 32, 42]
   >>> rec_ternary_search(0, len(test_list), test_list, 3)
   -1
   >>> rec_ternary_search(4, len(test_list), test_list, 42)
   8
   >>> rec_ternary_search(0, 2, [4, 5, 6, 7], 4)
   0
   >>> rec_ternary_search(0, 3, [4, 5, 6, 7], -10)
   -1
   >>> rec_ternary_search(0, 1, [-18, 2], -18)
   0
   >>> rec_ternary_search(0, 1, [5], 5)
   0
   >>> rec_ternary_search(0, 2, ['a', 'c', 'd'], 'c')
   1
   >>> rec_ternary_search(0, 2, ['a', 'c', 'd'], 'f')
   -1
   >>> rec_ternary_search(0, 0, [], 1)
   -1
   >>> rec_ternary_search(0, 3, [.1, .4 , -.1], .1)
   0


.. py:data:: precision
   :value: 10


.. py:data:: user_input