searches.ternary_search¶

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¶

`precision`
`user_input`

Functions¶

`ite_ternary_search`(→ int)	Iterative method of the ternary search algorithm.
`lin_search`(→ int)	Perform linear search in list. Returns -1 if element is not found.
`rec_ternary_search`(→ int)	Recursive method of the ternary search algorithm.

Module Contents¶

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

searches.ternary_search.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¶

leftint: left index bound.
rightint: right index bound.
arrayList[int]: List of elements to be searched on
targetint: 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

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

searches.ternary_search.precision = 10¶

searches.ternary_search.user_input¶