Pular para o conteúdo principal
Interactive Algorithm Education

Visualize & Master Algorithms & Data Structures

Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.

Search Visualizer

Ternary Search

Speed 100ms
Size 15
Difficulty ★★★★★ Beginner
Best For Small or unsorted datasets
Step Progress 0 / 0
Comparisons 0
Target —
Status Ready
Playback Paused
Out of Range
Search Range
Probe / Mid
Found
Step Explanation

Select an algorithm, enter a target value, and click 'Search' to begin.

Pseudocode 
 
 
  
 
 
 When to Use 
 

Select an algorithm to see recommended use cases.

 
 
 
 History 
 

Select an algorithm to see its history.

 
 
 
 
  
 
 
Ternary Search
  
 
  Elementary (2/5)
 
~35 minutes   Trisection with two midpoints  Divide-and-conquer variant  O(log₃ n) comparisons  Better suited for unimodal functions  
Prereqs: Binary Search, Big-O analysis  
 
Quick Reference
Ternary Search
Ternary Search is a divide-and-conquer algorithm that splits the search interval into three equal parts and uses two midpoints to narrow down the target region. It is less efficient than Binary Search in practice despite the same asymptotic behavior.

Difficulty: Elementary (2/5)
Stablesearching
Complexity
Best Time
O(1)
Average Time
O(log₃ n)
Worst Time
O(log₃ n)
Space
O(1)
When to Use
When searching unimodal functions or in contexts where dividing into three parts provides faster convergence (e.g., finding a peak in a unimodal array).
Pros
  • Works on sorted arrays with guaranteed convergence
  • Conceptually simple extension of Binary Search
  • Useful for optimization of unimodal functions
Cons
  • More comparisons per iteration than Binary Search
  • Slower in practice than Binary Search for sorted array search
  • Requires sorted input
History
Ternary Search has been known since the early days of computer science. It is closely related to the binary search family and is often taught as a conceptual variant.
 
 
If Binary Search splits the search space in two, Ternary Search splits it in three — using two midpoints and discarding one third of the range at a time.


The surprise: this is not faster — fewer rounds, but more comparisons per round. Ternary Search’s real home isn’t array lookup at all. It’s finding the peak of a unimodal function, where two midpoints let you decide which side of the peak you’re on.


How It Works


    

  1. Divide the interval into three equal parts using two midpoints: mid1 and mid2.
    2. 

  2. If the target equals either midpoint, return it.
    3. 

  3. If the target is smaller than mid1, search the leftmost third.
    4. 

  4. If the target is larger than mid2, search the rightmost third.
    5. 

  5. Otherwise, search the middle third between the midpoints.
    6. 

  6. Repeat until the interval is empty or the target is found.
    7. 



Key Insight


For sorted-array search, Ternary Search is mathematically worse than binary search.


    

  • Ternary round: two comparisons, removes 1/3 of the range.
    • 

  • Binary round: one comparison, removes 1/2 of the range.
    • 



log₂(n) vs 2·log₃(n) ≈ 1.26·log₂(n) — ternary search always does about 26% more work.


But for unimodal functions (a single peak, like a mountain), ternary search is the classic tool. Evaluate the function at both midpoints — the smaller (for minima) or larger (for maxima) value tells you which third can’t contain the optimum.


Worked Example


Search for 6 in [1, 3, 4, 6, 8, 9, 11, 12, 15, 17]:


    

  • [0, 9]: mid1=3 (6), mid2=6 (11). arr[3]=6 → return 3
    • 



Search for 7:


    

  • [0, 9]: mid1=3 → 6 < 7; mid2=6 → 11 > 7 → middle third [4, 5]
    • 

  • [4, 5]: mid1=4 → 8 > 7 → left third [4, 3] — empty → return -1
    • 



In the visualizer, two midpoints highlight simultaneously and the range snaps to one of the three thirds.


Edge Cases & Pitfalls


    

  • Empty interval — return -1 before computing midpoints.
    • 

  • Target exactly at a midpoint — caught directly: the base case.
    • 

  • mid1 == mid2 — on tiny intervals the midpoints collide. Handle gracefully by checking the remaining one or two elements.
    • 

  • Don’t confuse sorted search with optimization — for plain lookup, binary search is strictly better. Use ternary search only for unimodal optimization, not matching.
    • 

  • Non-unimodal functions — three-way splitting gives no correctness guarantee when multiple local peaks exist.
    • 



Comparison With Other Searches































ScenarioTernary SearchBinary SearchLinear Search
Comparisons (sorted)2·log₃(n) ≈ 1.26·log₂(n)log₂(n) — fewerO(n)
Unimodal optimizationBest toolNot applicableO(n) sampling
Requires sorted inputYes (for lookup)YesNo


Applications


    

  • Finding the maximum/minimum of a unimodal function (peak detection, resource allocation curves)
    • 

  • Peak finding in arrays that increase then decrease (mountain arrays)
    • 

  • Educational contrast with binary search — teaches why splitting into more than two parts doesn’t help for lookup
    • 



Practice Trajectory


    

  1. Hand-trace Ternary Search for target 9 in [2, 4, 6, 8, 9, 10, 12, 14], showing both midpoints each round.
    2. 

  2. Prove that ternary search needs more comparisons than binary search for the same array.
    3. 

  3. Use ternary search to find the maximum of f(x) = -x² + 10x on [0, 10].
    4. 

  4. Explain why two midpoints are necessary for unimodal optimization.
    5. 

  5. Implement ternary search for a lookup, then adapt it to a maximization routine.
    6.