Ternary Search Algorithm

A step-by-step guide to how Ternary Search works, why it divides a sorted array into three parts instead of two, and how it compares to Binary Search — with pseudocode, a Python implementation, and a live visualization you can run with your own numbers.

Interactive Visualization

Watch how Ternary Search narrows down the search range, iteration by iteration, using the array [3, 7, 12, 18, 24, 31, 39, 45, 52, 60, 71] and target 45 discussed later in this article. The animation starts automatically; use the controls to pause, step through manually, change the speed, or try your own sorted array and target.

Introduction

A searching algorithm is simply a method for finding out whether a particular value exists in a collection of data, and if so, where it is. Searching sounds simple, but the way you search matters a great deal once the data gets large. Checking every element one by one works, but it gets slow as the array grows. Efficient searching algorithms exist precisely to avoid that slowdown.

Ternary Search is one such algorithm. Like Binary Search, it is a divide-and-conquer technique: instead of scanning an array from start to end, it repeatedly shrinks the region it needs to look at. The idea that gives Ternary Search its name is straightforward: rather than splitting the sorted search space into two halves, it splits it into three roughly equal parts on every step, using two midpoints instead of one.

This article walks through exactly how that splitting works, shows a full worked example, gives you working pseudocode and Python code, and finishes with an interactive visualization so you can watch the algorithm run on any sorted array and target you choose.

What Is Ternary Search?

Ternary Search is a search algorithm that works on a sorted array. Sorting is a requirement, not a suggestion — the algorithm relies on being able to tell which direction the target lies in relative to a given position, and that only makes sense when the data is ordered.

Where Binary Search picks one midpoint and asks "is the target in the left half or the right half?", Ternary Search picks two midpoints, called mid1 and mid2, and asks a three-way question: is the target in the left third, the right third, or the middle third?

Given a search range from index left to index right, the two midpoints are calculated as:

mid1 marks the boundary between the left third and the middle third. mid2 marks the boundary between the middle third and the right third. Together they split the current range into three roughly equal sections, which is where the "ternary" in Ternary Search comes from.

How Ternary Search Works

The full procedure, from start to finish, looks like this:

1. Start with boundaries left = 0 and right = length − 1.
2. Calculate mid1.
3. Calculate mid2.
4. Compare the target with arr[mid1].
5. Compare the target with arr[mid2].
6. If the target equals arr[mid1], return mid1.
7. If the target equals arr[mid2], return mid2.
8. If the target is smaller than arr[mid1], it can only be in the left third, so eliminate everything from mid1 onward.
9. If the target is larger than arr[mid2], it can only be in the right third, so eliminate everything up to mid2.
10. Otherwise, the target must be between the two midpoints, so search only the middle third.
11. Repeat until the search range becomes empty (left > right), at which point the target is not in the array.

The key insight is the same one that makes Binary Search fast: every step throws away a large chunk of the array without ever looking at it. Ternary Search just throws away two-thirds of the remaining range each time instead of one half.

Step-by-Step Example

Take the sorted array [3, 7, 12, 18, 24, 31, 39, 45, 52, 60, 71] (indices 0 through 10) and search for the target value 60.

Notice how the active search range shrinks quickly: 11 elements, then 3, then 1. That is the divide-and-conquer effect at work. You can watch this exact kind of shrinking happen live in the visualization at the top of this page.

Ternary Search Formula

The two formulas at the heart of the algorithm are:

These are written this way, rather than as simpler-looking expressions, to avoid indexing mistakes. In code, division between integers should use integer (floor) division, so mid1 and mid2 always land on valid array indices instead of producing fractional positions that would need to be rounded separately.

Ternary Search Algorithm: Pseudocode

TERNARY_SEARCH(array, target)
    left ← 0
    right ← length(array) - 1

    WHILE left ≤ right
        third ← (right - left) / 3
        mid1  ← left + third
        mid2  ← right - third

        IF array[mid1] = target
            RETURN mid1

        IF array[mid2] = target
            RETURN mid2

        IF target < array[mid1]
            right ← mid1 - 1

        ELSE IF target > array[mid2]
            left ← mid2 + 1

        ELSE
            left  ← mid1 + 1
            right ← mid2 - 1

    RETURN -1

Ternary Search in Python

Here is a complete, iterative Python implementation:

def ternary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        third = (right - left) // 3
        mid1 = left + third
        mid2 = right - third

        if arr[mid1] == target:
            return mid1
        if arr[mid2] == target:
            return mid2

        if target < arr[mid1]:
            right = mid1 - 1
        elif target > arr[mid2]:
            left = mid2 + 1
        else:
            left = mid1 + 1
            right = mid2 - 1

    return -1  # target not found

This version is iterative: it uses a while loop rather than calling itself, so it runs in constant extra space. A recursive version is also possible — each recursive call would simply narrow left and right the same way and call itself again on the reduced range.

Walking through the edge cases:

• Target at the beginning: the range keeps shrinking toward the left third until mid1 or mid2 lands exactly on index 0.
• Target at the end: the same happens on the right side, shrinking toward the final index.
• Target in the middle: found quickly, often on the very first comparison against mid1 or mid2.
• Target not present: left eventually becomes greater than right, the loop ends, and the function returns -1.
• Empty array: right starts at -1, which is already less than left (0), so the loop never runs and -1 is returned immediately.
• One-element array: left and right are both 0, so mid1 and mid2 both equal 0 as well, and the single element is checked directly.

Time Complexity

Every call to Ternary Search does a small, constant amount of work — two midpoint calculations and up to two comparisons — and then continues on a range that is roughly one third the size of the previous one. That gives the recurrence:

Solving this recurrence, the number of times you can divide n by 3 before reaching 1 is log₃ n, so:

In Big-O notation this is usually simplified and written as O(log n). That is not a mistake or an approximation for convenience — logarithms with different bases only differ from one another by a constant multiplying factor (log₃ n = log n / log 3), and Big-O notation ignores constant factors. So O(log₃ n) and O(log n) describe the same growth rate.

Space Complexity

The iterative implementation shown above uses a fixed number of variables (left, right, mid1, mid2) regardless of the array size, so its space complexity is O(1). A recursive implementation would instead use O(log n) space, because each recursive call adds a new frame to the call stack, and the recursion depth grows logarithmically with the size of the array.

Ternary Search vs Binary Search

It's tempting to assume that dividing an array into three parts must be faster than dividing it into two, but that isn't the case. Ternary Search does more comparison work on every step, which offsets the benefit of a smaller remaining range.

Because log₃ n is smaller than log₂ n, Ternary Search needs fewer iterations — but each iteration costs up to two comparisons instead of one. Worked out in full, Ternary Search ends up doing more total comparisons on average than Binary Search for the same array. This is exactly why Binary Search, not Ternary Search, is the standard choice for searching an ordinary sorted array.

Advantages of Ternary Search

• Follows a clean divide-and-conquer structure that is easy to reason about.
• Runs in logarithmic time, so it scales well as the array grows.
• A useful teaching example of splitting a search space into more than two parts.
• In its optimization form (covered below), it is genuinely useful for finding the maximum or minimum of certain mathematical functions.

Limitations of Ternary Search

• Only works on data that can be ordered and searched — it needs a sorted array (or a well-behaved function, for the optimization variant).
• Performs more comparisons per iteration than Binary Search.
• Rarely the first choice for everyday sorted-array searching, since Binary Search is simpler and typically does less total work.
• More complicated to implement correctly than Binary Search, with more index arithmetic to get right.
• Provides no benefit on unsorted arrays without first sorting them, which itself costs extra time.

When Should You Use Ternary Search?

It helps to separate two different things that both go by the name "Ternary Search":

• Ternary Search on a sorted array — the version described throughout this article, used to locate a specific value's index. For this task, Binary Search is generally the better everyday tool.
• Ternary Search for optimization — a related but different technique used to find the maximum or minimum point of a unimodal function (a function that increases and then decreases, or vice versa, with a single peak or valley). Here, the same three-way narrowing idea is genuinely useful and is used in numerical optimization and competitive programming.

If you are searching a sorted list for a value, reach for Binary Search. If you are hunting for the peak or trough of a unimodal function, the optimization variant of Ternary Search is a solid choice.

Conclusion

Ternary Search is a natural extension of the divide-and-conquer idea behind Binary Search: instead of one midpoint, it uses two, and instead of two partitions, it works with three. It runs in O(log n) time and demonstrates multi-way partitioning clearly, which makes it a valuable algorithm to study — even though Binary Search remains the more efficient everyday choice for searching a sorted array. Where Ternary Search genuinely earns its place is in optimization problems over unimodal functions, a distinct but related use of the same three-way narrowing idea.

Frequently Asked Questions