Ternary Search Implementation
Below is the implementation of Ternary Search in Python:
def ternary_search(func, left, right, absolute_precision=1e-9):
"""
Perform ternary search to find the maximum value of a unimodal function within the given range.
Parameters:
func (callable): The unimodal function to be maximized.
left (float): The left endpoint of the search range.
right (float): The right endpoint of the search range.
absolute_precision (float): The absolute precision used for termination (default: 1e-9).
Returns:
float: The x-coordinate of the maximum value within the given range.
"""
while right - left > absolute_precision:
mid1 = left + (right - left) / 3
mid2 = right - (right - left) / 3
if func(mid1) < func(mid2):
left = mid1
else:
right = mid2
return (left + right) / 2
# Example usage:
def f(x):
return -(x - 3) ** 2 + 5 # Example unimodal function
max_x = ternary_search(f, 0, 5) # Searching within the range [0, 5]
max_y = f(max_x)
print("Maximum value at x =", max_x, "with y =", max_y)
Output
Maximum value at x = 2.9999999791391057 with y = 5.0
Time Complexity: The time complexity of Ternary Search is O(2 * log3(N)) where N is the number of iterations required to achieve the desired precision.
Auxiliary Space: Ternary Search has a space complexity of O(1) since it operates with constant space, regardless of the input size.
Ternary Search in Python
Ternary Search is a searching technique used to determine the minimum or maximum of a Unimodal function. Ternary Search divided the search space into three parts and then remove one of the three parts to reduce the search space.