Back to Searching

Ternary Search Visualizer

Watch how Ternary Search divides the array into three parts, eliminating 2/3 of the search space at each step.

Time: O(log₃ n)
Space: O(1)
Requirement: Sorted Array
Three-way Division
Search Range: [0, 14] | Comparisons: 0
0
1
L
1
5
2
8
3
10
4
15
5
20
6
25
7
30
8
35
9
40
10
45
11
50
12
55
13
60
14
65
R
Target: 25 | Step: 1 of 0

Current Step:

Click Start to begin Ternary Search visualization

Ternary Search

Time Complexity:O(log₃ n)
Space Complexity:O(1)
Comparisons:2 per iteration
Division:Three parts

Color Legend

Mid Points (M1, M2)
Search Boundaries (L, R)
Target Found
Active Search Space
Eliminated Space

vs Binary Search

Ternary:2 comparisons/step
Binary:1 comparison/step
Elimination:2/3 vs 1/2

Despite eliminating more space, ternary search typically performs more total comparisons than binary search.

How It Works

  1. 1Divide array into three equal parts
  2. 2Check both mid points (mid1, mid2)
  3. 3Eliminate 2/3 of search space
  4. 4Repeat on remaining 1/3

Python Implementation

def ternary_search(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    
    if left > right:
        return -1
    
    # Divide array into three parts
    mid1 = left + (right - left) // 3
    mid2 = right - (right - left) // 3
    
    # Check if target is at mid1 or mid2
    if arr[mid1] == target:
        return mid1
    if arr[mid2] == target:
        return mid2
    
    # Search in appropriate third
    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)

Real-world Applications

  • • Finding peaks in unimodal functions
  • • Optimization problems in mathematics
  • • Game theory and decision trees
  • • Scientific computing simulations
  • • When elimination rate matters more
  • • Educational purposes for algorithm analysis