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.

Ternary Search Algorithm:

1. Initialize Endpoints:
   • Set the left and right endpoints of the search range.
2. Iterative Division:
   • Divide the search interval into three parts by calculating two midpoints, mid1 and mid2.
   • Determine the function values at mid1 and mid2.
3. Update Endpoints:
   • Update the search range based on the function values at mid1 and mid2.
   • If the function value at mid1 is less than the value at mid2, update the left endpoint to mid1.
   • Otherwise, update the right endpoint to mid2.
4. Termination:
   • Repeat steps 2-3 until the difference between the left and right endpoints is smaller than a predefined absolute precision.
5. Result:
   • Return the midpoint between the final left and right endpoints as the x-coordinate of the maximum or minimum value.

Ternary Search Illustration:

Consider the function f(x)=−(x−3)^2+5. We want to find the maximum value of this function within the range [0, 5].

1. Initialization:
   • Set the left endpoint left=0 and the right endpoint right=5.
2. Iterative Division:
   • Calculate midpoints mid1 and mid2:
     • mid1=left+3right−left​
     • mid2=right−3right−left​
   • Evaluate function values at mid1 and mid2:
     • f(mid1)=f(1.666)=3.888
     • f(mid2)=f(3.333)=4.555
3. Update Endpoints:
   • Since f(mid1)<f(mid2), update left=mid1.
4. Iterative Division (Next Iteration):
   • Repeat steps 2-3 until the difference between left and right is smaller than the absolute precision.
5. Termination:
   • Once the termination condition is met, return the midpoint between the final left and right endpoints as the x-coordinate of the maximum value.

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)

Maximum value at x = 2.9999999791391057 with y = 5.0

Time Complexity: The time complexity of Ternary Search is O(2 * log₃(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.