```
"""
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)
"""
import sys
# This is the precision for this function which can be altered.
# It is recommended for users to keep this number greater than or equal to 10.
precision = 10
# This is the linear search that will occur after the search space has become smaller.
def lin_search(left, right, A, target):
for i in range(left, right + 1):
if A[i] == target:
return i
# This is the iterative method of the ternary search algorithm.
def ite_ternary_search(A, target):
left = 0
right = len(A) - 1
while True:
if left < right:
if right - left < precision:
return lin_search(left, right, A, target)
oneThird = (left + right) / 3 + 1
twoThird = 2 * (left + right) / 3 + 1
if A[oneThird] == target:
return oneThird
elif A[twoThird] == target:
return twoThird
elif target < A[oneThird]:
right = oneThird - 1
elif A[twoThird] < target:
left = twoThird + 1
else:
left = oneThird + 1
right = twoThird - 1
else:
return None
# This is the recursive method of the ternary search algorithm.
def rec_ternary_search(left, right, A, target):
if left < right:
if right - left < precision:
return lin_search(left, right, A, target)
oneThird = (left + right) / 3 + 1
twoThird = 2 * (left + right) / 3 + 1
if A[oneThird] == target:
return oneThird
elif A[twoThird] == target:
return twoThird
elif target < A[oneThird]:
return rec_ternary_search(left, oneThird - 1, A, target)
elif A[twoThird] < target:
return rec_ternary_search(twoThird + 1, right, A, target)
else:
return rec_ternary_search(oneThird + 1, twoThird - 1, A, target)
else:
return None
# This function is to check if the array is sorted.
def __assert_sorted(collection):
if collection != sorted(collection):
raise ValueError("Collection must be sorted")
return True
if __name__ == "__main__":
user_input = input("Enter numbers separated by coma:\n").strip()
collection = [int(item) for item in user_input.split(",")]
try:
__assert_sorted(collection)
except ValueError:
sys.exit("Sequence must be sorted to apply the ternary search")
target_input = input("Enter a single number to be found in the list:\n")
target = int(target_input)
result1 = ite_ternary_search(collection, target)
result2 = rec_ternary_search(0, len(collection) - 1, collection, target)
if result2 is not None:
print("Iterative search: {} found at positions: {}".format(target, result1))
print("Recursive search: {} found at positions: {}".format(target, result2))
else:
print("Not found")
```