ternary search Algorithm
The ternary search algorithm is an advanced searching technique that aims to find the minimum or maximum value of a unimodal function or determine the position of a specific target value within a sorted array. The algorithm is based on the divide and conquer strategy, where it divides the search interval into three equal parts and subsequently evaluates the function at two intermediate points. By comparing the function values at these points, the algorithm narrows down the search interval to one of the three sub-intervals, which contains the desired minimum or maximum value.
The efficiency of the ternary search algorithm lies in its ability to discard a significant portion of the search interval with each iteration, thereby reducing the number of comparisons required to locate the target value. This results in a logarithmic time complexity of O(log3 N), where N represents the size of the search interval. Although the ternary search algorithm performs fewer iterations compared to the binary search algorithm, it requires evaluating the function at two points, which can make it less efficient than binary search in certain scenarios. Nevertheless, the ternary search algorithm is an effective approach for solving optimization problems and searching through large datasets with a unimodal structure.
"""
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(f"Iterative search: {target} found at positions: {result1}")
print(f"Recursive search: {target} found at positions: {result2}")
else:
print("Not found")
