Ternary Search

Ternary search is a divide-and-conquer search algorithm that divides the search space into three parts instead of two, similar to binary search.

Algorithm

The algorithm divides the array into three parts by computing two midpoints, and then determines which third contains the target element.

Time Complexity

Ternary search has a time complexity of $O({\log }_{3}n)$, which is asymptotically equivalent to $O(\log n)$ but with a larger constant factor than binary search.

When would you actually use it?

For finding an element in a sorted array: never — and it is worth seeing why. Each binary-search step spends 1 comparison to keep 1/2 of the array; each ternary step spends 2 comparisons to keep 1/3. Total comparisons: binary needs log₂ n, ternary needs 2·log₃ n ≈ 1.26·log₂ n — about 26% more work for the same answer, every time. Cutting the array into more pieces is not free; you pay for it in probes.

The real habitat of ternary search is a different problem: finding the peak of a unimodal function — one that rises and then falls (or falls then rises). There, binary search cannot work even in principle: probing a single point tells you the height, but not which side of the peak you are on. Two interior probes do: whichever probe is lower, the peak cannot be in the piece beyond it, so a third of the interval is safely discarded per round. This version shows up constantly in optimization tasks — tuning a parameter with a convex cost, geometry problems that minimize a distance, competitive-programming problems of the form "maximize f(x) over an interval." Its refined cousin, golden-section search, places the two probes so that one of them can be reused next round — the same idea with the redundant evaluation squeezed out.

Implementation

def ternary_search(arr, target, left, right):
    if right >= left:
        # Divide the array into three parts
        third = (right - left) // 3
        mid1 = left + third
        mid2 = right - third
        
        # Check if the target is at one of the mid points
        if arr[mid1] == target:
            return mid1
        if arr[mid2] == target:
            return mid2
        
        # Determine which part to search in
        if target < arr[mid1]:
            return ternary_search(arr, target, left, mid1 - 1)
        elif target > arr[mid2]:
            return ternary_search(arr, target, mid2 + 1, right)
        else:
            return ternary_search(arr, target, mid1 + 1, mid2 - 1)
    
    return -1

# Wrapper function to simplify usage
def search(arr, target):
    return ternary_search(arr, target, 0, len(arr) - 1)

# Example usage
if __name__ == "__main__":
    arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
    target = 15
    result = search(arr, target)
    
    if result != -1:
        print("Element found at index {}".format(result))
    else:
        print("Element not found")