Overview
Ternary Search repeatedly removes one third of a range when a function rises then falls, or falls then rises.
CoreSource checked
Ternary Search
Finds an optimum in a unimodal range by comparing two interior points.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Searching
- Difficulty
- Intermediate
- Family
- Interval Search
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
candidate searchobjective functionnumeric approximationinterval searchcandidate spacematch testsearch interval
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(log n)
Average
O(log n)
Worst
O(log n)
Space
O(1)
When to Use
- Use Ternary Search when you need to split a numeric range into thirds.
- Use it when the input assumptions match the method's model.
- Use it when you need a clear lookup strategy for known input organization.
- Use it when the method's tradeoffs fit the workload.
When Not to Use
- Avoid it when maintaining the required data layout costs more than the lookup saves.
- Avoid it when the required output is not approximate minimum or maximum location.
What It Does
- Splits a numeric range into thirds
- Keeps the side that can still contain the optimum
Use Cases
- Optimizing unimodal functions
- Search over continuous ranges
- Competitive programming optimization
Inputs
- Unimodal function
- Search interval
- Stopping tolerance
Outputs
- Approximate minimum or maximum location
Key Formulas (1)
Third points
m1 = low + (high − low) / 3; m2 = high − (high − low) / 3
m1 = low + (high - low) / 3; m2 = high - (high - low) / 3Splits a unimodal search interval into thirds.
Pseudocode
- 1.Choose two interior points that split the interval into thirds
- 2.Evaluate the function at both points
- 3.Discard the third that cannot contain the optimum
- 4.Repeat until the interval is small enough
Canonical Example
- Input
- values = [2, 5, 8, 12, 16], target = 12
- Output
- index = 3
- Explanation
- Ternary Search: The search checks candidate positions until it identifies the target value.
Implementation Notes
- Keep the input contract explicit: Unimodal function; Search interval; Stopping tolerance.
- Decide up front whether not-found results return null, -1, false, or an insertion position.
- Search algorithms should define both success and failure semantics.
Common Pitfalls
- Ternary Search assumes the function is unimodal over the search interval.
- Handle empty, invalid, and boundary inputs before trusting approximate minimum or maximum location.
- Off-by-one bounds, duplicates, and missing-target behavior should be specified before implementation.
Interactive Mechanism Walkthrough
Indexed Interval & Boundary ProbeShow an interval shrinking around a single peak or valley.
Target key: 41low=0, mid=4, high=9
4[0]
9[1]
15[2]
22[3]
27[4]
34[5]
41[6]
49[7]
58[8]
63[9]
Step 1 of 4: Choose two interior points that split the interval into thirds
ternary-intervalNotes
Ternary Search operates in O(log n) time and O(1) space within the Interval Search family. Key governing relation: m1 = low + (high - low) / 3; m2 = high - (high - low) / 3. Often compared with Binary Search and Bisection Method.
Sources (1)
What each reference supports for this entry.
The Art of Computer Programming, Volume 3
BookSearching reference for Ternary Search's probe strategy, comparison model, and expected or worst-case behavior.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageAlternative toBinary Search
Ternary search and binary search both narrow ordered domains under different objective assumptions.
Related Algorithms
Tags
SearchOptimizationNumerical Methods