Ternary Search Algorithm

Ternary search divides the search interval into three parts using two midpoints. It is mostly used to find the extremum (minimum/maximum) of a unimodal function. For searching a specific value in a sorted array, binary search is generally preferred.

Time Complexity

O(log n)

Base change doesn't affect Big-O

Space Complexity

O(1)

Iterative approach

Comparisons/Iter

Versus 1 for binary search

Practical Note

Often slower than binary search

Target

Comparisons

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

mid1

mid2

Range

Found

How Ternary Search Works

Steps

1. Compute two midpoints m1 and m2 splitting [l, r] into thirds
2. If target equals arr[m1] or arr[m2], return index
3. If target < arr[m1], search left third [l, m1-1]
4. Else if target > arr[m2], search right third [m2+1, r]
5. Otherwise search middle third [m1+1, m2-1]

When to Use

• Optimizing unimodal functions (continuous ternary search)
• Educational comparison with binary search
• Rarely recommended for exact lookups in arrays

Implementation

def ternary_search(arr, target):
    l, r = 0, len(arr) - 1
    comparisons = 0
    while l <= r:
        third = (r - l) // 3
        m1 = l + third
        m2 = r - third
        comparisons += 2
        if arr[m1] == target:
            return m1
        if arr[m2] == target:
            return m2
        if target < arr[m1]:
            r = m1 - 1
        elif target > arr[m2]:
            l = m2 + 1
        else:
            l = m1 + 1
            r = m2 - 1
    return -1

arr = [1, 2, 4, 4, 7, 9, 12, 15, 17, 18, 21, 24, 27, 30, 32, 35, 40, 42, 45, 50]
print(ternary_search(arr, 24))

Note: For locating a specific value in sorted arrays, binary search typically performs fewer comparisons overall.

Previous: Exponential Search Back to Searching Index