AlgoViz

Back to All Algorithms
Ternary Search
Category: Searching | Time: O(log3 n) | Space: O(1)
Visualization
Visual representation of the data structure
About Ternary Search

A divide and conquer searching technique. It is similar to binary search but divides the array into three parts and determines which part the key lies in.

Code Editor
The code is for reference. Editing it won't affect the visualization.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Variable State
{
  "arr": "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]",
  "target": 5,
  "l": 0,
  "r": 9
}
Ternary Search: How It Works
Last updated October 28, 2026

Overview

Ternary Search splits the sorted range into three parts using two probes, mid1 and mid2. Depending on how the target compares with these two values, it keeps the left third, the right third, or the middle third.

Although it discards two-thirds of the range per step, it needs up to two comparisons to do so, which makes it slightly slower than binary search for searching sorted arrays. Its real strength is a different problem: finding the maximum or minimum of a unimodal function, where binary search does not apply directly.

In the default example (1..10, target 5), the first probes are index 3 (value 4) and index 6 (value 7). Since 5 lies between them, the range narrows to indices 4..5, and the next probe finds 5 at index 4.

Step by step

  1. Set l = 0 and r = n - 1.
  2. While l <= r, compute mid1 = l + floor((r - l) / 3) and mid2 = r - floor((r - l) / 3).
  3. If either probe equals the key, return its index.
  4. If the key is below arr[mid1], search l..mid1-1; if above arr[mid2], search mid2+1..r; otherwise search mid1+1..mid2-1.
  5. If the range becomes empty, return -1.

Complexity

CaseCostWhy
Best caseO(1)A probe hits the target immediately.
Average caseO(log3 n)Two-thirds of the range is discarded per iteration.
Worst caseO(log3 n)About 2·log3(n) comparisons, more than binary search's log2(n).
Extra spaceO(1)Iterative implementation.

When to use it

  • Finding the peak or valley of a unimodal function or array, such as an optimal price or launch angle.
  • Optimisation over continuous ranges where you can evaluate the function but not its derivative.
  • Learning: it is a good way to understand why binary search is optimal for sorted lookups.

Common mistakes

  • Using it for plain sorted lookups is usually a de-optimisation compared with binary search.
  • On functions with flat regions it cannot tell which side to discard.
  • For continuous ranges, a fixed iteration count is safer than a floating-point equality check.
Worked Example: Ternary Search Dry Run
Generated from the same trace that drives the visualizer above, using the default input.

A dry run is the best way to check your understanding of Ternary Search: follow each row, predict the next one, and compare. The run below takes 13 steps in total. Steps that only re-print loop counters are left out so the decisions stand out. The Line column refers to the line numbers in the code listing above.

Input
1,2,3,4,5,6,7,8,9,10
Target
5
Result
return value = 4
StepLineArrayWhat happens
11[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]target = 5, l = 0, r = 9
22[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]l = 0, r = 9, condition = 9 >= 0
56[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]mid1 = 3, condition = 4 == 5
68[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]mid2 = 6, condition = 7 == 5
711[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]target = 5, mid1 = 3, condition = 5 < 4
92[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]l = 4, r = 5, condition = 5 >= 4
126[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]mid1 = 4, condition = 5 == 5
137[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]return value = 4
Frequently Asked Questions
About Ternary Search

What is Ternary Search?

Ternary Search is a divide-and-conquer search algorithm that finds an element in a sorted array by repeatedly dividing the search space into three parts instead of two.

How does Ternary Search work?

It calculates two middle points, `mid1` and `mid2`, which divide the array into three equal parts. It then compares the target with the elements at `mid1` and `mid2` to decide which of the three sub-arrays to continue searching in.

What is its primary use case?

While it can be used on sorted arrays, its most common application is to find the minimum or maximum of a unimodal function (a function that strictly increases and then strictly decreases, or vice versa).

What is the time complexity of Ternary Search?

The time complexity is O(log3 n). While the base of the logarithm is larger than in Binary Search (log2 n), this does not represent a significant performance improvement. In fact, it is often slower.

Why is Ternary Search often slower than Binary Search?

Although the number of recursive calls is smaller (log3 n vs log2 n), Ternary Search requires two comparisons per iteration, while Binary Search only needs one. The extra comparison per step makes it less efficient than Binary Search for array searching.

What is the space complexity?

The space complexity is O(1) for the iterative version and O(log n) for the recursive version.

Does the array need to be sorted?

Yes, for finding an element in an array, the array must be sorted.

How does it compare to Jump Search?

Binary Search is almost always better than both, but comparing the two, their performance depends on the array size and data distribution. Jump Search's O(√n) is generally worse than Ternary Search's O(log3 n).

When should one absolutely use Ternary Search?

The main practical application is for finding the extremum (min/max) of a unimodal function, where you cannot simply check the middle and decide which half to discard. In this scenario, it is a very effective algorithm.

How many comparisons are made in the worst case per iteration?

In the worst case, two comparisons are made: one against `ar[mid1]` and another against `ar[mid2]`.

Where can I learn more?

You can find a more detailed explanation on GeeksforGeeks.