Ternary Search Algorithm
- Initialize Endpoints:
- Set the left and right endpoints of the search range.
- Iterative Division:
- Divide the search interval into three parts by calculating two midpoints,
mid1
andmid2
. - Determine the function values at
mid1
andmid2
.
- Divide the search interval into three parts by calculating two midpoints,
- Update Endpoints:
- Update the search range based on the function values at
mid1
andmid2
. - If the function value at
mid1
is less than the value atmid2
, update the left endpoint tomid1
. - Otherwise, update the right endpoint to
mid2
.
- Update the search range based on the function values at
- Termination:
- Repeat steps 2-3 until the difference between the left and right endpoints is smaller than a predefined absolute precision.
- Result:
- Return the midpoint between the final left and right endpoints as the x-coordinate of the maximum or minimum value.
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.