Introduction
Ternary Search is an algorithm to find the minimum or maximum of a unimodal function. In Binary Search, the array is divided into two parts while in Ternary Search, the array is divided into three parts.
Implementation
Searching minimum
while left <= right:
mid1 = left + (right - left) // 3
mid2 = right - (right - left) // 3
if cost(mid1) <= cost(mid2):
right = mid2 - 1
else:
left = mid1 + 1
return left
Searching maximum
while left <= right:
mid1 = left + (right - left) // 3
mid2 = right - (right - left) // 3
if cost(mid1) >= cost(mid2):
right = mid2 - 1
else:
left = mid1 + 1
return left
Complexity
- Time complexity: for the search function
- Space complexity: